OutsideR_ @ 2021-05-05 16:23:29

#include <iostream>
#include <queue>
using namespace std;
short n,x1,x2,y1,y2;
char map[1001][1001];
short mx[4]={1,-1,0,0};
short my[4]={0,0,1,-1};
bool visit[1001][1001];
struct road{
    short x,y,step;
};
void bfs(int x1,int y1){
    queue <road> que;
    road first;
    first.x=x1;
    first.y=y1;
    first.step=0;
    visit[x1][y1]=1;
    que.push(first);
    while(!que.empty()){
        road f=que.front();
        que.pop();
        if(f.x==x2 && f.y==y2){
            cout<<f.step<<endl;
            exit(0);
        }
        for(int i = 0;i<4;i++){
            short tx=f.x+mx[i];
            short ty=f.y+my[i];
            if(!visit[tx][ty] && map[tx][ty]=='0' && tx<=n && tx>=1 && ty<=n && ty>=1){
                road n;
                n.x=tx;
                n.y=ty;
                n.step=f.step+1;
                visit[tx][ty];
                que.push(n);
            }
        }
    }
}
int main(){
    cin>>n;
    for(short i = 1;i<=n;i++)for(short j = 1;j<=n;j++)cin>>map[i][j];
    cin>>x1>>y1>>x2>>y2;
    bfs(x1,y1);
    return 0; 
} 

by EuphoricStar @ 2021-05-05 16:29:54

@Cyc曹 这样试试

#include <iostream>
#include <queue>
using namespace std;
int n,x1,x2,y1,y2;
char map[1005][1005];
int mx[4]={1,-1,0,0};
int my[4]={0,0,1,-1};
bool visit[1005][1005];
struct road{
    int x,y,step;
};
void bfs(int x1,int y1){
    queue <road> que;
    road first;
    first.x=x1;
    first.y=y1;
    first.step=0;
    visit[x1][y1]=1;
    que.push(first);
    while(!que.empty()){
        road f=que.front();
        que.pop();
        if(f.x==x2 && f.y==y2){
            cout<<f.step<<endl;
            return;
        }
        for(int i = 0;i<4;i++){
            int tx=f.x+mx[i];
            int ty=f.y+my[i];
            if(!visit[tx][ty] && map[tx][ty]=='0'){
                road n;
                n.x=tx;
                n.y=ty;
                n.step=f.step+1;
                visit[tx][ty] = 1; // 修改
                que.push(n);
            }
        }
    }
}
int main(){
    cin>>n;
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n;j++){
            cin>>map[i][j];
        }
    }
    cin>>x1>>y1>>x2>>y2;
    bfs(x1,y1);
    return 0; 
} 

by reailikezhu @ 2021-05-05 16:30:44

不用 short 能行吗？ short 不大好用。 空间复杂度上没啥问题吧

by OutsideR_ @ 2021-05-05 16:30:50

刚刚自己也发现了 谢谢大佬

by reailikezhu @ 2021-05-05 16:31:14

@zltzlt 咱俩想法是相同的

by OutsideR_ @ 2021-05-05 16:31:25

@reailikezhu 没错 主要是没有标记

visit[tx][ty]

by reailikezhu @ 2021-05-05 16:32:24

@Cyc曹 是。