DFS/BFS
1. 79. 单词搜索
中等
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例 1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" 输出：true
示例 2：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE" 输出：true
示例 3：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB" 输出：false
提示：
m == board.lengthn = board[i].length1 <= m, n <= 61 <= word.length <= 15board和word仅由大小写英文字母组成
// 定义一个Solution类，用于解决二维网格中查找单词的问题
class Solution {
public:
// 定义四个方向的移动向量，分别对应上、右、下、左
int dx[4]{1,0,-1,0};
int dy[4]{0,-1,0,1};
// 使用深度优先搜索（DFS）和回溯算法来查找单词
bool dfs(vector<vector<char>>& board, string word, int k, int i, int j, vector<vector<int>> &visit) {
// 如果当前字符不匹配，直接返回false
if(word[k] != board[i][j]) {
return false;
} else if (k == word.size() - 1) {
// 如果已经匹配到最后一个字符，返回true
return true;
}visit[i][j] = 1; // 标记当前位置为已访问
bool result = false;
// 遍历四个方向
for (int d{}; d < 4; ++d) {
// 计算新的位置
int i1 = i + dx[d];
int j1 = j + dy[d];// 检查新位置是否在网格内
if (min(i1, j1) < 0 || i1 >= board.size() || j1 >= board[0].size()) {
continue;
}// 如果新位置已被访问过，跳过
if (1 == visit[i1][j1]) continue;// 递归搜索新位置
if (dfs(board, word, k + 1, i1, j1, visit)) {
result = true;
break;
}
}
visit[i][j] = 0; // 回溯，将当前位置标记为未访问
return result;
}// 主函数，用于判断网格中是否存在给定的单词
bool exist(vector<vector<char>>& board, string word) {
int m = board.size(), n = board[0].size();
vector<vector<int>> visit(m, vector<int>(n)); // 初始化访问标记矩阵
// 遍历网格的每个位置，以每个位置为起点进行DFS
for (int i{}; i < m; ++i) {
for (int j{}; j < n; ++j) {
bool flag{false};
flag = dfs(board, word, 0, i, j, visit);
if (flag) return true;
}
}
return false;
}
};
解释：
这段代码首先定义了四个方向的移动向量，然后在dfs函数中，它递归地搜索每个可能的方向，直到找到匹配的单词或者确定单词不存在。exist函数遍历网格的每个位置，以每个位置为起点调用dfs函数进行搜索。如果dfs函数返回true，则表示找到了单词，exist函数也会返回true。如果遍历完整个网格都没有找到单词，则exist函数返回false。
