原始笔记已经记下了”DFS + 回溯算法”和”main 循环结束后也要回溯 flag”的关键点。这里在不改代码的前提下，把题意和标准的回溯模板写完整。
题目背景
LeetCode 79「单词搜索」。给一个 m × n 的字符网格 board 和一个目标单词 word，判断能否在网格中按水平/垂直相邻的方式拼出 word。同一格子在一次拼接中不能重复使用。
概念解释
- DFS（深度优先搜索）：沿着一条路径深入，走不通再回退尝试别的方向。
- 回溯（backtracking）：DFS 中”走过又退回”时，必须把状态（这里是”该格是否已被本次路径占用”的
flag标记）复原，否则会污染兄弟分支。 - 方向数组：网格四邻域问题常用
(±1, 0)/(0, ±1)四个偏移；本笔记把四个方向直接展开成四段if，逻辑等价。
实现原理
- 在
exist中双重循环枚举每个起点(i, j)，若board[i][j] == word[0]，则把该格flag置 1，调用dfs(...,1,ended)尝试匹配后续字符。 dfs(arr, flag, i, j, word, k, ended)的语义是”已经匹配了word[0..k-1]，当前停在(i, j)“，目标是匹配word[k]：- 若
k == word.size()即已全匹配，置ended = true返回； - 否则尝试
(i, j-1) / (i-1, j) / (i+1, j) / (i, j+1)四个邻居，命中且未被占用就标记flag后递归，递归返回后立刻把flag清回 0，这就是回溯。
- 若
- 起点自身的
flag也必须在dfs返回后清 0（无论是否命中），否则后续起点会受影响——这正是原文提示”main 函数 for 循环完成后也需要回溯 flag”的原因。 - 一旦
ended为真就直接返回true，提前结束所有搜索。
最坏时间复杂度 O(m·n·4^L)，其中 L = word.size()；空间复杂度 O(L) 递归栈 + O(m·n) 的 flag 数组。
参考实现
解题思路: dfs + 回溯算法
需要注意的点：main函数内for循环完成后，也需要回溯flag的值
class Solution {
private:
void dfs(const std::vector<std::vector<char>>& arr, std::vector<std::vector<int>>& flag, int i, int j, const std::string& word,int k, bool& ended)
{
// std::cout << "i = " << i << " j = " << j << " k = " << k << std::endl;
if (k == word.size())
{
ended = true;
return;
}
if (i > -1 && i < arr.size() && (j - 1) > -1 && (j - 1) < arr[0].size())
{
//std::cout << "i = " << i << " j - 1 " << j - 1 << std::endl;
if (!flag[i][j - 1] && arr[i][j - 1] == word[k])
{
flag[i][j - 1] = 1;
dfs(arr,flag,i,j-1,word,k+1, ended);
flag[i][j - 1] = 0;
}
}
if ( (i-1) > -1 && (i-1) < arr.size() && j > -1 && j < arr[0].size())
{
//std::cout << "i-1 = " << i-1 << " j " << j << std::endl;
if (!flag[i-1][j] && arr[i-1][j] == word[k])
{
flag[i-1][j] = 1;
dfs(arr, flag, i-1, j , word, k + 1, ended);
flag[i-1][j] = 0;
}
}
if (i+1 > -1 && i+1 < arr.size() && j > -1 && j < arr[0].size())
{
//std::cout << "i + 1 = " << i + 1 << " j " << j << std::endl;
if (!flag[i+1][j] && arr[i+1][j] == word[k])
{
flag[i+1][j] = 1;
dfs(arr, flag, i+1, j, word, k + 1, ended);
flag[i+1][j] = 0;
}
}
if (i > -1 && i < arr.size() && j + 1 > -1 && j + 1 < arr[0].size())
{
//std::cout << "i = " << i << " j + 1 " << j + 1 << std::endl;
if (!flag[i][j + 1] && arr[i][j + 1] == word[k])
{
flag[i][j + 1] = 1;
dfs(arr, flag, i, j + 1, word, k + 1, ended);
flag[i][j + 1] = 0;
}
}
//return false;
}
public:
bool exist(vector<vector<char>>& board, string word) {
std::vector<std::vector<int>> flag(board.size(), std::vector<int>(board[0].size(),0));
bool ended = false;
for (int i = 0; i < board.size(); ++i)
{
for (int j = 0; j < board[0].size(); ++j)
{
ended = false;
if (board[i][j] == word[0])
{
flag[i][j] = 1;
dfs(board,flag,i,j,word,1,ended);
flag[i][j] = 0;
if (ended)
{
std::cout << ended << std::endl;
return true;
}
}
}
}
return false;
// std::cout << ended << std::endl;
}
};
