广搜求条

违规用户名K&xs3Z^ @ 2024-08-20 09:00:38

#include<bits/stdc++.h>
using namespace std;
queue<int> x;
queue<int> y;
char a[1110][1110];
int step=-1,n,s1,t1,s2,t2;
bool vis[1110][1110];
int fx[6]={0,0,1,0,-1};
int fy[6]={0,1,0,-1,0};
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>a[i][j];
    cin>>s1>>t1>>s2>>t2;
    x.push(s1),y.push(t1);
    while(!x.empty()){
        for(int i=1;i<=4;i++){
        int tx=x.front()+fx[i];
        int ty=y.front()+fy[i];
        if(a[tx][ty]=='0'&&!vis[tx][ty]){
            vis[tx][ty]=1;
            a[tx][ty]='1';
            step++;
            x.push(tx),y.push(ty);
            if(tx==s2&&ty==t2){
                cout<<step<<endl;
                return 0;
            }
        }
        }
        x.pop(),y.pop();
    }
    return 0;
}

by 违规用户名K&xs3Z^ @ 2024-08-20 09:01:42

@FIRESTARS gengen队 需要我们！ QWQ

by FIRESTARS @ 2024-08-20 09:02:29

@违规用户名K&xs3Z^ 我来了

by Whitecrane @ 2024-08-20 09:02:46

#include<bits/stdc++.h>
using namespace std;
char a[1100][1100];
int m,n;
int sx,sy,ex,ey;
int fx[5]={0,0,1,0,-1};
int fy[5]={0,1,0,-1,0};
int q[1000300][4];
int main()
{
    int h=1,t=1;
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    cin>>sx>>sy>>ex>>ey;
    a[sx][sy]='1';
    q[1][1]=sx;
    q[1][2]=sy;
    q[1][3]=0;
    int tx,ty;
    while(h<=t){
        for(int i=1;i<=4;i++){
            tx=q[h][1]+fx[i];
            ty=q[h][2]+fy[i];
            if(a[tx][ty]=='0'){
                a[tx][ty]='1';
                t++;
                q[t][1]=tx;
                q[t][2]=ty;
                q[t][3]=q[h][3]+1;
                if(tx==ex&&ty==ey){
                    cout<<q[t][3]<<endl;
                    return 0;
                }
            }
        }
        h++;
    }
}

by Whitecrane @ 2024-08-20 09:03:53

用什么队列啊，数组就行

by FIRESTARS @ 2024-08-20 09:04:09

@违规用户名K&xs3Z^ 你的步数记录有问题

by FIRESTARS @ 2024-08-20 09:04:49

@违规用户名K&xs3Z^ 并不是说这是第几个被加入队列的格子这就是从起始点到他的步数

by 违规用户名K&xs3Z^ @ 2024-08-20 09:05:05

@FIRESTARS ok 窝看看

by FIRESTARS @ 2024-08-20 09:05:30

@违规用户名K&xs3Z^

hack:

3
000
000
000
1 1 3 3 

by tireden @ 2024-08-20 09:05:37

楼上正解

by Deeplove_lzs @ 2024-08-20 09:05:57

https://www.luogu.com.cn/paste/b88ji1co