回溯法。
class Solution {
public:
int n, m;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
bool check(int x, int y) {
return x >= 0 && x < n && y >= 0 && y < m;
}
bool dfs(int x, int y, int idx, string &word, vector<vector<char>> &board) {
if (word[idx] != board[x][y]) return false;
if (idx == word.size() - 1) return true;
char t = board[x][y];
board[x][y] = ‘ ‘;
for (int i = 0; i < 4; i++) {
int a = x + dx[i], b = y + dy[i];
if (check(a, b))
if (dfs(a, b, idx + 1, word, board))
return true;
}
board[x][y] = t; // 回溯
return false;
}
bool exist(vector<vector<char>>& board, string &word){
n = board.size(), m = board[0].size();
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (dfs(i, j, 0, word, board))
return true;
return false;
}
};