20分求助,dfs出现异常
  • 板块P1238 走迷宫
  • 楼主Engulf
  • 当前回复9
  • 已保存回复9
  • 发布时间2021/7/1 21:27
  • 上次更新2023/11/4 20:26:53
查看原帖
20分求助,dfs出现异常
482728
Engulf楼主2021/7/1 21:27

求助!

dfs搜索,但连样例都没过

本蒟蒻初学算法,比各位神犇写的代码垃圾多了,千万不要嫌弃

dfs代码贴上:

#include <iostream>
using namespace std;
const int N=20;
bool visit[N][N];
bool mp[N][N];
int a[50005][2];
int sx,sy,fx,fy;
int ans=0;

int step=1;

int n,m;

int dx[]={0,-1,0,1,0};
int dy[]={0,0,-1,0,1};

inline void print()
{
    cout<<"("<<a[0][0]<<","<<a[0][1]<<")";
    for(int i=1;a[i][0]!=0 && a[i][1]!=0;i++){
        cout<<"->"<<"("<<a[i][0]<<","<<a[i][1]<<")";
    }
    cout<<endl;
}

void dfs(int x,int y)
{
    if(x==fx && y==fy)
    {
        
        print();
        ans++;
        return;
    }
    else
    {
        for(int i=1;i<=4;i++){
            int nx=x+dx[i];
            int ny=y+dy[i];
            if(mp[nx][ny] && !visit[nx][ny])
            {
                step++;
                a[step][0]=nx;
                a[step][1]=ny;
                visit[nx][ny]=true;
                dfs(nx,ny);
                visit[nx][ny]=false;
                step--;
            }
        }
    }
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>mp[i][j];
        }
    }
    cin>>sx>>sy;
    cin>>fx>>fy;
    a[0][0]=sx;
    a[0][1]=sy;
    dfs(sx,sy);
    if(ans==0)cout<<"-1"<<endl;
    return 0;
}

指教!

2021/7/1 21:27
加载中...