广搜求条

违规用户名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 _WHITE_NIGHT_ @ 2024-08-20 09:23:12

@违规用户名K&xs3Z^ 你初始的那个点vis没有赋值

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

@LikablePie79015 嗷嗷 懂了懂了 原来是用用别的数组来代存步数哇

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

@_WHITENIGHT 改啦改啦 这个好像不用标记的 两种方式都A了 待会试试结构体 谢谢dalao 不麻烦啦

#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;
int 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';
            vis[tx][ty]=vis[x.front()][y.front()]+1;
            x.push(tx),y.push(ty);
            if(tx==s2&&ty==t2){
                cout<<vis[tx][ty]<<endl;
                return 0;
            }
        }
        }
        x.pop(),y.pop();
    }
    return 0;
}

by _WHITE_NIGHT_ @ 2024-08-20 09:29:23

@违规用户名K&xs3Z^

刚把你代码改好(哭笑不得)

#include<bits/stdc++.h>
using namespace std;
struct Node {
    int x,y,st;
};
queue <Node> q;
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;

    vis[s1][t1] = 1;
    q.push({s1,t1,0});
    while(!q.empty()) {
        auto tmp = q.front();
        int x = tmp.x,y = tmp.y,st = tmp.st;
        if(x==s2&&y==t2) {
            cout<<st<<endl;
            return 0;
        }
        for(int i=1; i<=4; i++) {
            int tx=x+fx[i];
            int ty=y+fy[i];
            if(a[tx][ty]=='0' && !vis[tx][ty]) {
                vis[tx][ty]=1;
                q.push({tx,ty,q.front().st+1});

            }
        }
        q.pop();
    }
    return 0;
}

by _WHITE_NIGHT_ @ 2024-08-20 09:30:44

有点想起那时候学bfs时的感觉了（逃

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

@_WHITENIGHT 谢谢给出的结构体方法 哈哈

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

@_WHITENIGHT 窝要努力到dalao的高度

by _WHITE_NIGHT_ @ 2024-08-20 09:35:01

@违规用户名K&xs3Z^ 我也是蒟蒻qwq