给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
] 给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.
#include "_000库函数.h"
//此问题是一个DFS问题，每个单词可以像上下左右四个方向进行下一步行走
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
if (board.empty() || board[].empty())return false;
int m = board.size(), n = board[].size();
vector<vector<bool>>visted(m, vector<bool>(n, false));//记录是否被访问过
for (int i = ; i < m; ++i) {
for (int j = ; j < n; ++j) {
if (search(board, visted, , i, j, word))return true;//每个单词单元都进行上下左右进行搜索！
}
}
}
bool search(vector<vector<char>>& board, vector<vector<bool>>& visted, int idx, int i, int j, string word) {
if (idx == word.size())return true;
int m = board.size(), n = board[].size();
if (i < || j < || i >= m || j >= n || visted[i][j] || board[i][j] != word[idx])return false;
visted[i][j] = true;
bool res = (search(board, visted, idx + , i - , j, word) ||
search(board, visted, idx + , i + , j, word) ||
search(board, visted, idx + , i, j - , word) ||
search(board, visted, idx + , i, j + , word));
visted[i][j] = false;//回溯
return res;
}
};
void T079() {
Solution s;
vector<vector<char>> board;
string word;
board = { {'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'} };
word = "ABCCED";
cout << s.exist(board, word) << endl;
}