初学dfs，求dalao加回溯为什么错

sll00 @ 2024-03-01 17:00:56

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn=1000;
ll bu[4][2]={{1,0},{-1,0},{0,1},{0-1}};
char arr[maxn][maxn];
int n, m,nx,ny,dx,dy,wall;
bool judge=false;
void dfs(int nx,int ny)
{
    if((nx<1||ny<1||nx>n||ny>m))
        return;
    if(nx==n&&ny==m)
    {
        judge=true;
        return;
    }
    if(judge)
        return;
    for(int i =0;i<4;i++)
    {
        if(arr[nx+bu[i][0]][ny+bu[i][1]]!='#')
        {
            arr[nx+bu[i][0]][ny+bu[i][1]]='#';
            dfs(nx+bu[i][0],ny+bu[i][1]);

        //arr[nx+bu[i][0]][ny+bu[i][1]]='.';
        }

    }
    return;
}
int main()
{
    nx=1,ny=1;
    cin>>n>>m;
    dx=n,dy=m;
    for(int i =1;i<=n;i++)
    {
        for(int j =1;j<=m;j++)
        {
            cin>>arr[i][j];
            if(arr[i][j]=='#')
                wall++;
        }
    }
    //事前剪枝
    if(n*m-wall-2<abs(dx-nx)+abs(dy-ny)-1)
        cout<<"No";
    else
    {
        arr[nx][ny]='#';
        dfs(nx,ny);
        if(judge)
            cout<<"Yes";
        else
            cout<<"No";
    }
    return 0;
}

by ilibilib @ 2024-03-01 17:08:11

@sll00 好像只用 dfs 出起点和终点联不联通吧，不用求最短路线，加回溯也没有意义吧

by QBW1117 @ 2024-03-01 17:15:14

@sll00

建议使用bfs，因为这里不求最短路径，回溯也没有意义，bfs能更高效的解决连通性的问题，且bfs不用递归调用栈空间，不会MLE，所以，建议了解一下BFS[doge]

by shoot_down @ 2024-03-01 17:23:18

@sll00 加个读入优化：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn=1000;
ll bu[4][2]={{1,0},{-1,0},{0,1},{0-1}};
char arr[maxn][maxn];
int n, m,nx,ny,dx,dy,wall;
bool judge=false;
void dfs(int nx,int ny)
{
    if((nx<1||ny<1||nx>n||ny>m))
        return;
    if(nx==n&&ny==m)
    {
        judge=true;
        return;
    }
    if(judge)
        return;
    for(int i =0;i<4;i++)
    {
        if(arr[nx+bu[i][0]][ny+bu[i][1]]!='#')
        {
            arr[nx+bu[i][0]][ny+bu[i][1]]='#';
            dfs(nx+bu[i][0],ny+bu[i][1]);

        //arr[nx+bu[i][0]][ny+bu[i][1]]='.';
        }

    }
    return;
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    nx=1,ny=1;
    cin>>n>>m;
    dx=n,dy=m;
    for(int i =1;i<=n;i++)
    {
        for(int j =1;j<=m;j++)
        {
            cin>>arr[i][j];
            if(arr[i][j]=='#')
                wall++;
        }
    }
    //事前剪枝
    if(n*m-wall-2<abs(dx-nx)+abs(dy-ny)-1)
        cout<<"No";
    else
    {
        arr[nx][ny]='#';
        dfs(nx,ny);
        if(judge)
            cout<<"Yes";
        else
            cout<<"No";
    }
    return 0;
}

by CaoXian @ 2024-03-01 17:29:17

@sll00

如果你说的“回溯”是指被注释掉的一句的话。

回溯都是对搜索的正确性的补充，常常会有第一次搜索搜不到正确解或最优解的情况，并且很多时候你想要继续搜索而下一步状态在之前被修改过，无法使用。回溯就是在搜索结束后将状态退回到搜索前，以保证之后的搜索可以正常进行。

你这一句将已遍历的位置撤销回未遍历的状态，就表示你希望它在下一次被访问到的时候可以继续搜索。而针对这道题的情况，它无论什么时候被访问到，最后搜索出来的局面一定相同，所以这是不必要的并且在时间复杂度上是错误的。

（仅仅就这题而言，不撤销修改可以理解为记忆化。）

其次，你的事前剪枝完全不必要，几乎没有优化作用。

by CaoXian @ 2024-03-01 17:30:00

@shoot_down 怎么什么事情都是个读入优化可以解决的，汗。

by sll00 @ 2024-03-01 18:09:33

@ilibilib 是的，我也看了其他帖子有的说这道题要回溯有的说不要的，一时难以接受，谢谢大佬

by sll00 @ 2024-03-01 18:10:27

@QBW1117 好的，过后补写bfs版本的，谢谢你

by sll00 @ 2024-03-01 18:13:26

@VividCycle 感谢大佬，这个事前剪枝确实没什用，是自己在初学的时候看到要剪枝操作然后就写的。谢谢大佬对回溯的讲解，初学dfs以为都得回溯

by CaoXian @ 2024-03-01 18:14:04

@sll00 不是，dfs 跟 bfs 没啥区别啊，你要知道回溯不是优化而是正确性的保障，而且只有 dfs 才能回溯，你改 bfs 对于你的问题治标不治本啊。

by sll00 @ 2024-03-01 18:15:27

@shoot_down 这个题读入数据，好像并不是很多，加快可能也是杯水车薪，主要还是那个回溯把时间复杂度提上去了，但还是谢谢你的回答