大佬们康康 40分的

B3625 迷宫寻路

Tania2013 @ 2024-06-09 18:20:52

#include<bits/stdc++.h>
using namespace std;
int x[4]={0,0,1,-1},y[4]={1,-1,0,0};
char a[110][110];
int n,m,vis[105][105];
int flag=0;
void dfs(int x1, int y1)
{
    if(x1==n && y1==m)
    {
        flag=1;
        return;
    }
    for(int i=1;i<=4;i++)
    {
        int x2=x1+x[i],y2=y1+y[i];
        if (x2>=1 && x2<=n && y2>=1 && y2<=m && a[x2][y2]=='.' && vis[x2][y2]==0)
        {
            vis[x2][y2]=1;
            dfs(x2,y2);
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
        }
    }
    vis[1][1]=1;
    dfs(1,1);
    if(flag)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
    return 0;
}

by renzhanwen @ 2024-06-09 18:32:07

@Tania2013 第20行后面要加vis[x2][y2]=0;这段代码，否则这个dfs是没法走第一次走过的路的，这样是在清除标记。求关！！！

by Prodige @ 2024-06-09 18:34:36

你深搜时的遍历下标错了

for(int i=1;i<=4;i++) //这里
    {
        int x2=x1+x[i],y2=y1+y[i];
        if (x2>=1 && x2<=n && y2>=1 && y2<=m && a[x2][y2]=='.' && vis[x2][y2]==0)
        {
            vis[x2][y2]=1;
            dfs(x2,y2);
        }
    }

应该改成这样

for(int i=0;i<4;i++) //this
    {
        int x2=x1+x[i],y2=y1+y[i];
        if (x2>=1 && x2<=n && y2>=1 && y2<=m && a[x2][y2]=='.' && vis[x2][y2]==0)
        {
            vis[x2][y2]=1;
            dfs(x2,y2);
        }
    }

by Tania2013 @ 2024-06-09 19:06:44

谢谢

|