class Solution { public: bool exist(vector<vector<char> > &board, string word) { if (word.empty()) return true; if (board.empty() || board[0].empty()) return false; vector<vector<bool> > visited(board.size(), vector<bool>(board[0].size(), false)); for (int i = 0; i < board.size(); ++i) { for (int j = 0; j < board[i].size(); ++j) { if (search(board, word, 0, i, j, visited)) return true; } } return false; } bool search(vector<vector<char> > &board, string word, int idx, int i, int j, vector<vector<bool> > &visited) { if (idx == word.size()) return true; if (i < 0 || j < 0 || i >= board.size() || j >= board[0].size() || visited[i][j] || board[i][j] != word[idx]) return false; visited[i][j] = true; bool res = search(board, word, idx + 1, i - 1, j, visited) || search(board, word, idx + 1, i + 1, j, visited) || search(board, word, idx + 1, i, j - 1, visited) || search(board, word, idx + 1, i, j + 1, visited); visited[i][j] = false; return res; } };
|