1 class Solution { 2 public: 3     bool exist(vector<vector<char>>& board, string word) { 4         vector<vector<int>> visited(board.size(), vector<int>(board[0].size(), 0)); 5         for (int i = 0; i < board.size(); ++i) { 6             for (int j = 0; j < board[0].size(); ++j) { 7                 if (dfs(board, visited, word, i, j, 0)) return true; 8             } 9         }10         return false;11     }12 private:13     bool dfs(vector<vector<char>>& board, vector<vector<int>>& visited, string word, int x, int y, int pos)14     {15         if (!visited[x][y]) {16             if (board[x][y] == word[pos]) {17                 visited[x][y] = 1;18                 if (pos == word.size() - 1) return true;19                 else {20                     if (x + 1 < board.size() && !visited[x + 1][y] && dfs(board, visited, word, x + 1, y, pos + 1)) return true;21                     if (x - 1 >= 0 && !visited[x - 1][y] && dfs(board, visited, word, x - 1, y, pos + 1)) return true;22                     if (y + 1 < board[0].size() && !visited[x][y + 1] && dfs(board, visited, word, x, y + 1, pos + 1)) return true;23                     if (y - 1 >= 0 && !visited[x][y - 1] && dfs(board, visited, word, x, y - 1, pos + 1)) return true;24                 }25                 visited[x][y] = 0;26             }27             else {28                 return false;29             }30         }31         return false;32     }33 };