class Solution {
public:
bool exist(vector<vector<char>>& board, string word)
{
int m = board.size(), n = board[0].size();
for (int i = 0; i < m; ++i)
{
for (int j = 0; j < n; ++j)
{
if (board[i][j] == word[0] && backtracking(board, word, i, j, 0))
{
return true;
}
}
}
return false;
}
bool backtracking(vector<vector<char>>& board, string word, int i, int j, int start)
{
int m = board.size(), n = board[0].size();
if (i < 0 || j < 0 || i >= m || j >= n || board[i][j] != word[start])
{
return false;
}
if (start == word.size() - 1) return true;
char temp = board[i][j];
board[i][j] = '#';
bool res = backtracking(board, word, i + 1, j, start + 1) || \
backtracking(board, word, i - 1, j, start + 1) || \
backtracking(board, word, i, j + 1, start + 1) || \
backtracking(board, word, i, j - 1, start + 1);
board[i][j] = temp;
return res;
}
};