1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
if (board.empty() || board[0].empty() || word.empty()) return false;
m = board.size(), n = board[0].size();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (exist(board, i, j, word, 0)) return true;
}
}
return false;
}
bool exist(vector<vector<char>> &board, int i, int j, const string &word, int b) {
if (b == word.length()) return true;
if (i < 0 || j < 0 || i >= m || j >= n || board[i][j] != word[b]) return false;
board[i][j] = '#';
for (int k = 0; k < 4; ++k) {
if (exist(board, i + dy[k], j + dx[k], word, b + 1)) return true;
}
board[i][j] = word[b];
return false;
}
int m, n, dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};
};
|