Word Search

알파벳이 하나씩 써진 2차원 벡터와 찾아야하는 문자열 하나를 받는다.

2차원 보드에서 문자열 중 하나의 문자와 다음 문자는 인접(상하좌우)하고 있어야 한다.

또한 하나의 문자 칸은 두 번이상 사용될 수 없다.

class Solution {
public:
    static const int MAX_LENGTH = 6;

    int _yLength = 0;
    int _xLength = 0;

    bool DFS(int index, int &x, int &y, bool visited[][MAX_LENGTH], vector<vector<char>>& board, string &word)
    {
        static const int DIRECTION = 4;
        static const int DIRECTION_X[DIRECTION]{0, 0, -1, 1};
        static const int DIRECTION_Y[DIRECTION]{-1, 1, 0, 0};

        if (word.size() == index++ + 1)
        {
            return true;
        }

        for (int i = 0; i < DIRECTION; i++)
        {
            int nextX = x + DIRECTION_X[i];
            int nextY = y + DIRECTION_Y[i];

            if (nextX < 0 || nextY < 0 || _xLength <= nextX || _yLength <= nextY)
            {
                continue;
            }

            if (visited[nextY][nextX] || word[index] != board[nextY][nextX])
            {
                continue;
            }

            visited[nextY][nextX] = true;

            if (DFS(index, nextX, nextY, visited, board, word))
            {
                return true;
            }

            visited[nextY][nextX] = false;

        }
        return false;
    }


    bool exist(vector<vector<char>>& board, string word) {

        bool visited[MAX_LENGTH][MAX_LENGTH]{};

        _yLength = board.size();
        _xLength = board.back().size();

        for (int y = 0; y < _yLength; y++)
        {
            for (int x = 0; x < _xLength; x++)
            {
                if (word.front() == board[y][x])
                {
                    visited[y][x] = true;
                    if (DFS(0, x, y, visited, board, word))
                    {
                        return true;
                    }
                    visited[y][x] = false;
                }
            }
        }

        return false;
    }
};