10分求助

Dream_weavers @ 2022-04-30 17:53:41

#include<iostream>
#define int long long
using namespace std;
const int N=1005;
int a[N][N];
int n,x1,x2,y1,y2,ans;
char qwq;
int py[4][2]={1,0,0,1,-1,0,0,-1};
void bfs(int x,int y,int cnt){
    if(x==x2&&y==y2){
        ans=max(ans,cnt);
        return ;
    }
    for(int i=0;i<4;i++){
        int kx=x+py[i][0];
        int ky=y+py[i][1];
        if(kx<1||ky<1||kx>n||ky>n||a[kx][ky])continue;
        a[kx][ky]='1';
        bfs(kx,ky,cnt+1);
        //a[kx][ky]='0';
    }
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>qwq,a[i][j]=qwq-'0';
    cin>>x1>>y1>>x2>>y2;
    a[x1][y1]=1;
    bfs(x1,y1,0);
    cout<<ans;
    return 0;
}

by _Remake_ @ 2022-04-30 17:57:49

ans=max(ans,cnt);

为什么要取max

by xzy090626 @ 2022-04-30 18:01:31

这题 DFS 过不了吧，得用 BFS

（您似乎写的是 DFS 诶）

by _Remake_ @ 2022-04-30 18:04:37

正常的bfs不是用队列做的吗qwq 递归似乎不太好做

by Dream_weavers @ 2022-04-30 18:05:49

谢谢

by 幸存者 @ 2022-04-30 18:10:54

这好像是一种新算法，dfs 与 bfs 融为一体。

by _Remake_ @ 2022-04-30 18:16:38

#include<bits/stdc++.h>
#define int long long int
using namespace std;
const int N=1234;
int a[N][N];
bool vis[N][N];
int n,x1,x2,Y1,y2;
char qwq[N];
int dx[4]={1,0,0,-1};
int dy[4]={0,-1,1,0};
queue<pair<int,pair<int,int> > >Q;
int bfs(int x,int y)
{
    Q.push(make_pair(x,make_pair(y,0)));
    while(Q.size())
    {
        int X=Q.front().first;
        int Y=Q.front().second.first;
        vis[X][Y]=1;
        int step=Q.front().second.second;
        if(X==x2&&Y==y2)
        {
            return step;
        }
        Q.pop();
        for(int r=0;r<=3;r++)
        {
            X+=dx[r];
            Y+=dy[r];
            if(!vis[X][Y]&&X>=1&&X<=n&&Y>=1&&Y<=n)
            {
                Q.push(make_pair(X,make_pair(Y,step+1)));
                vis[X][Y]=1;
            }
            X-=dx[r];
            Y-=dy[r];
        }
    }
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>(qwq+1);
       for(int j=1;j<=n;j++)
       {
            if(qwq[j]=='1')
            {
                vis[i][j]=1;
            }
       }
    }
    cin>>x1>>Y1>>x2>>y2;
    cout<<bfs(x1,Y1);
    return 0;
}

把您的代码魔改了亿下然后A了 qwq

by Dream_weavers @ 2022-04-30 18:19:18

此贴结，感谢各位，已经AC了