单词搜索游戏里能找到特定吗？
摘要：🧾 一、代码 #include <iostream> #include <vector> #include &a
🧾 一、代码
#include <iostream>
#include <vector>
#include <climits>
#include <cmath>
#include <unordered_set>
using namespace std;
int n, m;
bool flag = false;
void DFS(vector<vector<char>> &grid, int i, int j, string cur, string target)
{
if (cur.size() == target.size())
{
flag = true;
return;
}
int curidx = cur.size();
if (i < 0 || i > n - 1 || j < 0 || j > m - 1 || grid[i][j] != target[curidx])
{
return;
}
else
{
cur.push_back(grid[i][j]);
char temp = grid[i][j];
grid[i][j] = '#';
DFS(grid, i + 1, j, cur, target);
DFS(grid, i - 1, j, cur, target);
DFS(grid, i, j + 1, cur, target);
DFS(grid, i, j - 1, cur, target);
grid[i][j] = temp;
}
}
int main(int argc, char const *argv[])
{
cin >> n >> m;
vector<vector<char>> grid(n, vector<char>(m));
for (size_t i = 0; i < n; i++)
{
for (size_t j = 0; j < m; j++)
{
cin >> grid[i][j];
}
}
string cur;
string target;
getline(cin, target);
for (size_t i = 0; i < n; i++)
{
for (size_t j = 0; j < m; j++)
{
DFS(grid, i, j, cur, target);
if (flag)
{
break;
}
}
}
if (flag)
{
cout << "true" << endl;
}
else
{
cout << "false" << endl;
}
return 0;
}
🧠 二、核心算法：DFS + 回溯
DFS 负责探索所有可能路径。
回溯（backtracking） 在路径失败时还原之前状态。
每次递归会检查字符匹配情况，然后尝试四个方向的继续搜索。
🧭 三、搜索流程图（DFS）逻辑
下面是这段程序的执行逻辑流程图：
+--------------------------+
| 从主函数遍历每个单元格 |
+-----------+--------------+
|
v
+-------------------------------------+
| dfs(board, word, i, j, index=0) |
+--------+----------------------------+
|
+-------+--------+
| 检查边界条件和字符匹配 |
+-------+--------+
|
+---------v----------+
| 若 index == word.size |
| 返回 true（成功） |
+---------+----------+
|
+---------v----------+
| 标记当前为已访问（'#'）|
+---------+----------+
|
+---------v----------+
| 递归搜索四个方向 |
+---------+----------+
|
+---------v----------+
| 恢复字符（回溯） |
+---------+----------+
|
+---------v----------+
| 若任意方向成功则返回 true |
| 否则 false |
+------------------------+
🔁 这个过程在整个网格中从每个起点进行尝试，因此可以发现所有潜在路径。
🎯 四、测试案例（示例）
输入：
3 4
A B C E
S F C S
A D E E
ABCCED
可视化网格：
A B C E
S F C S
A D E E
输出：
true
解释：路径为 A → B → C → C → E → D（对应单词 ABCCED）。