MnZn求助,BFS正解,爆零

P1746 离开中山路

曾治茗 @ 2022-10-15 23:19:08

rt

#include<iostream>
#include<queue>
#include<cstdio>
#include<string.h>

using namespace std;

char a[1010][1010];
int st[1010][1010];
int ans=0,x1,x2,y1,y2,n;

struct point{
    int xx,yy;
};
queue <point> q;

void BFS(){
    q.push((point){x1,y1}); 

    while(!q.empty() ){

//      for(int i=1;i<=n;i++)
//      {
//          for(int j=1;j<=n;j++)
//          {
//              cout<<st[i][j];
//          }
//          cout<<endl;
//      }
//      cout<<endl;
        int cx=q.front().xx;
        int cy=q.front().yy;
        q.pop() ;

        if(cx>n || cx<1) continue;
        if(cy>n || cy<1) continue;
        if(st[cx][cy]==1) continue;
        if(a[cx][cy]=='1') continue;

        st[cx][cy]=1;

        if(cx==x2 && cy==y2){
            cout << ans;
            return;
        }

        ans++;

        q.push((point){cx+1,cy}); 
        q.push((point){cx-1,cy}); 
        q.push((point){cx,cy+1}); 
        q.push((point){cx,cy-1}); 
    }

}

int main(){
    memset(st,0,sizeof(st));

    cin >>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin >> a[i][j];
        }
    }
    cin >> x1 >>y1 >> x2 >> y2;
//  st[x1][y1]=1;
    BFS();

    return 0;
}
/*
3
0 0 1
1 0 1
1 0 0
1 1 3 3
*/

qwq


by LYM20114 @ 2022-10-17 19:21:30

入队前要判断坐标是否合法,给你看一下我的代码


by LYM20114 @ 2022-10-17 19:21:57


#include <iostream>
#include <queue>
using namespace std;
int n,sx,sy,ex,ey,ans;
char inp[1005][1005];
struct nod{
    int x,y;
};
queue <nod> q1;
queue <nod> q2;
int res[1005][1005];
int vis[1005][1005];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
bool check(int x,int y){
    if(x >= 1 && x <= n && y >= 1 && y <= n) return true;
    else return false;
}
int bfs(int x,int y){
    vis[x][y] = 1;q1.push(nod{x,y});
    vis[ex][ey] = 2;q2.push(nod{ex,ey});
    while(!q1.empty() && !q2.empty()){
        int s1 = q1.size(),s2 = q2.size(),nx,ny;
        bool flag = 0;
        if(s1 <= s2){
            flag = 0;nx = q1.front().x;ny = q1.front().y;
            q1.pop();
        }
        else{
            flag = 1;nx = q2.front().x;ny = q2.front().y;
            q2.pop();
        }
        for(int i = 0;i < 4;i++){
            int xx = nx + dx[i];
            int yy = ny + dy[i];
            if(check(xx,yy) && inp[xx][yy] == '0'){
                if(!res[xx][yy]){
                    res[xx][yy] = res[nx][ny] + 1;
                    vis[xx][yy] = vis[nx][ny];
                    if(!flag)  q1.push(nod{xx,yy});
                    else q2.push(nod{xx,yy});
                }
                else if(vis[xx][yy] + vis[nx][ny] == 3){
                    ans = res[xx][yy] + res[nx][ny];
                    return ans;
                }
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= n;j++)
            cin >> inp[i][j];
    cin >> sx >> sy >> ex >> ey;
    cout << bfs(sx,sy) + 1;
    return 0;
}

by _ZXWDS @ 2022-10-18 10:19:17

 q.push((point){cx+1,cy}); 
        q.push((point){cx-1,cy}); 
        q.push((point){cx,cy+1}); 
        q.push((point){cx,cy-1}); 

如果入队的时候你的cx,cy处于边界那么就会越界


|