算法 DFS
遇到的问题
我在写DFS的时候
for(int i = 0; i < 4; i ++)
{
int a = x + dx[i], b = y + dy[i];
if(a < 0 || a >= n || b < 0 || b >= n)continue;
if(g[a][b] == ‘#’)continue;
if(st[a][b])continue;
if(dfs(a, b))return true;
//dfs(a, b); 我写的是这种形式,后来想了想这样写是不对的, 因为你这样的话就算后续已经找到了出口,但是不能传到第一次dfs的地方所以WA掉了。
}
return false;
C++ 代码
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
char g[N][N];
bool st[N][N];
int n;
int l1, r1, l2, r2;
int dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};
bool dfs(int x, int y)
{
if(x == l2 && y == r2)return true;
st[x][y] = true;
for(int i = 0; i < 4; i ++)
{
int a = x + dx[i], b = y + dy[i];
if(a < 0 || a >= n || b < 0 || b >= n)continue;
if(g[a][b] == '#')continue;
if(st[a][b])continue;
if(dfs(a, b))return true;
}
return false;
}
int main()
{
int T;
cin >> T;
while(T --)
{
memset(st, false, sizeof st);
cin >> n;
for(int i = 0; i < n; i ++) cin >> g[i];
cin >> l1 >> r1 >> l2 >> r2;
if(g[l1][r1] == '#' || g[l2][r2] == '#')
{
puts("NO");
continue;
}
if(dfs(l1, r1))puts("YES");
else puts("NO");
}
return 0;
}
为什么不能在进入dfs之前就判断目标点是不是’#’啊,这样在dfs就不需要那么多次判断了啊
请问大佬,为啥dfs函数的倒数第二行代码:if(dfs(x,y))return true; 不可以换为 return dfs(x,y)?
if(dfs)这样dfs返回的不为真的话就往下继续找符合结果的,如果找到所有栈都退出,如果要写成return(turn)不管返回的是真是假都是直接退出了,这样写不一定能找到答案。
谢谢,明白了
为什么不用加回溯呀?st[a][b] 重新赋值为0
时间复杂度大概多少呢
想请教一下大佬,这个题为不用回溯啊。
这里每个格子是个状态,每个格子不会被重复搜索,所以不需要恢复原状。
它其实是回溯了能不能搜到。就是代码中的”return true”和”return false”。不回溯的话函数运行结束后是回到上一层函数。除非用指针,不然到底搜没搜到就是未知状态。
请问大佬,为啥dfs函数的倒数第二行代码:if(dfs(x,y))return true; 不可以换为 return dfs(x,y)?
因为dfs(x,y)为false的时候,又不一定返回false。只是说如果为true,肯定返回true,建议仔细理解代码的意思和多看视频,学习递归可以把它当成一棵树来看待。