79. Word Search
89.63%，dfs对图深搜，进行剪枝和回溯，注意几个点。
- 深搜的下一个点，可能在该点的上、下、左、右，所以可以利用两个数组
dx、dy，以及操作int x = cur_x + dx[i];int y = cur_y + dy[i];确定下一；个点； - 下一个点必须在图中；
- 下一个点不能在当前路径中被访问过，用vis数组进行标记；
好像是不建议使用全局变量的，下次尽量全用引用来代替；
class Solution {
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int m = 0, n = 0;
public:
bool exist(vector<vector<char>> &board, string word) {
int index = 0;
m = board.size();
if (m == 0) return word.empty();
n = board[0].size();
vector<vector<bool>> vis(m, vector<bool>(n));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (word[0] == board[i][j]) {
vis[i][j] = true;
bool ans = dfs(board, 1, word, i, j, vis);
vis[i][j] = false;
if (ans) return true;
}
}
}
return false;
}
bool dfs(vector<vector<char>> &board, int index, string &word, int cur_x, int cur_y, vector<vector<bool>> &vis) {
if (index >= word.length()) return true;
for (int i = 0; i < 4; i++) {
int x = cur_x + dx[i];
int y = cur_y + dy[i];
if (x >= 0 && x < m && y >= 0 && y < n) {
if (word[index] == board[x][y] && !vis[x][y]) {
vis[x][y] = true;
bool ans = dfs(board, index + 1, word, x, y, vis);
vis[x][y] = false;
if (ans) return true;
}
}
}
return false;
}
};
