单词搜索游戏里能找到特定吗？
摘要：🧾 一、代码 #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） 在路径失败时还原之前状态。
每次递归会检查字符匹配情况，然后尝试四个方向的继续搜索。