求助大佬

Mark_M @ 2022-02-13 14:37:07

#include<bits/stdc++.h>
using namespace std;
char c[1005][1005];
bool vis[1005][1005];
int dir[4][2]={{0,1},{0,-1},{-1,0},{1,0},};
int x_1,y_1,x_2,y_2;
int n;

struct Node{
    int x;
    int y;
    int step;
};

bool check(int x,int y){
    if(x<0||x>=n||y<0||y>=n||vis[x][y]==true||c[x][y]=='1'){
        return false;
    }
    return true;
}

int BFS(){
    queue<Node> Q;
    Node st={x_1,y_1,0};
    Q.push(st);
    vis[x_1][y_1]=true;

    while(!Q.empty()){
        Node p=Q.front();
        Q.pop();
        if(p.x==x_2&&p.y==y_2){
            return p.step;
        }
        for(int i=0;i<4;i++){
            int next_x=p.x+dir[i][0];
            int next_y=p.x+dir[i][1];
            if(check(next_x,next_y)){
                Node next_p={next_x,next_y,p.step+1};
                Q.push(next_p);
                vis[next_x][next_y]=true;
            }
        }
    }
}

int main(int argc, char** argv){
    memset(vis,false,sizeof(vis));
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>c[i][j];
        }
    }
    cin>>x_1>>y_1>>x_2>>y_2;

    int ans=BFS();
    cout<<ans;
    return 0;
}

by 神光qwq @ 2022-02-13 14:47:25

int next_y=p.x+dir[i][1]; 这行是p.y不是p.x啊

by coldy_rainy @ 2022-02-13 14:52:59

@Mark20091226

帮忙@

即这里：

int next_y=p.x+dir[i][1];

改成

int next_y=p.y+dir[i][1];

即可

by coldy_rainy @ 2022-02-13 14:56:48

@penhaochen

但还有3WA，正调莫急

by coldy_rainy @ 2022-02-13 15:19:54

@Mark20091226

AC代码：

#include<bits/stdc++.h>
using namespace std;
char c[1005][1005];
bool vis[1005][1005];
int dir[4][2]={{0,1},{0,-1},{-1,0},{1,0}};
int x_1,y_1,x_2,y_2;
int n;

struct Node{
    int x;
    int y;
    int step;
};

bool check(int x,int y){
    if(x<0||x>=n||y<0||y>=n||vis[x][y]==true||c[x][y]=='1'){
        return false;
    }
    return true;
}

int BFS(){
    queue<Node> Q;
    Node st={x_1,y_1,0};
    Q.push(st);
    vis[x_1][y_1]=true;

    while(!Q.empty()){
        Node p=Q.front();
        Q.pop();
        if(p.x==x_2&&p.y==y_2){
            return p.step;
        }
        for(int i=0;i<4;i++){
            int next_x=p.x+dir[i][0];
            int next_y=p.y+dir[i][1];
            if(check(next_x,next_y)){
                Node next_p={next_x,next_y,p.step+1};
                Q.push(next_p);
                vis[next_x][next_y]=true;
            }
        }
    }
}

int main(int argc, char** argv){
    memset(vis,false,sizeof(vis));
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>c[i][j];
        }
    }
    cin>>x_1>>y_1>>x_2>>y_2;
   x_1--;
   y_1--;
   x_2--;
   y_2--;
    int ans=BFS();
    cout<<ans;
    return 0;
}

原因：本题的起始点和终点坐标都是从1开始的，而你的代码是从0开始的，因此自减可以适应你这种代码

by Mark_M @ 2022-02-13 15:31:37

@penhaochen 3Q

by Mark_M @ 2022-02-13 15:38:48

@神光qwq 灰常感谢