80分，#3、#8挂了

_Kamisato_Ayaka_ @ 2022-05-04 08:38:36

#include<bits/stdc++.h>
using namespace std;
int n,sx,sy,fx,fy;
char mp[1005][1005];
int vis[1005][1005];
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
queue<int>qx;
queue<int>qy;
queue<int>step;
int main()
{
    int ans=0x7f7f7f7f;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>mp[i][j];
    cin>>sx>>sy>>fx>>fy;
    qx.push(sx);
    qy.push(sy);
    step.push(0);
    while(!qx.empty())
    {
        int x=qx.front();
        int y=qy.front();
        int st=step.front();
        for(int i=0;i<4;i++){
            int nx=x+dx[i];
            int ny=y+dy[i];
            if(nx<1||nx>n||ny<1||ny>n) continue;
            if(vis[nx][ny]==1||mp[nx][ny]==1) continue;
            qx.push(nx);
            qy.push(ny);
            step.push(st+1);
            vis[nx][ny]=1;
            if(nx==fx && ny==fy){
                ans=min(ans,st+1);
                continue;
            }
        }
        qx.pop();
        qy.pop();
        step.pop();
    }
    cout<<ans<<endl;
    return 0;
}

by 快斗游鹿 @ 2022-05-04 09:45:01

@YZP_AK_IOI

if(vis[nx][ny]==1||mp[nx][ny]==1) continue;

要改为

if(vis[nx][ny]==1||mp[nx][ny]=='1') continue;

因为你 mp 是 char 类型，不是 int。其他见下

by 快斗游鹿 @ 2022-05-04 09:47:32

一点小优化

#include<bits/stdc++.h>
using namespace std;
int n,sx,sy,fx,fy;
char mp[1005][1005];
int vis[1005][1005];
int dx[10]={1,0,-1,0};
int dy[10]={0,1,0,-1};
queue<int>qx;
queue<int>qy;
queue<int>step;
int main()
{
    int ans=10000000;
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>mp[i][j];
    cin>>sx>>sy>>fx>>fy;
    qx.push(sx);
    qy.push(sy);
    step.push(0);
    while(!qx.empty()&&!qy.empty()&&!step.empty())
    {
        int x=qx.front();
        int y=qy.front();
        int st=step.front();
        qx.pop();
        qy.pop();
        step.pop();
        if(x==fx&&y==fy){//放在外面判断能优化时间
            cout<<st;return 0;    
        }
        for(int i=0;i<4;i++){
            int nx=x+dx[i];
            int ny=y+dy[i];
            if(nx<1||nx>n||ny<1||ny>n) continue;
            if(vis[nx][ny]==1||mp[nx][ny]=='1') continue;
            qx.push(nx);
            qy.push(ny);
            step.push(st+1);
            vis[nx][ny]=1;
        }
    }
    return 0;
}

by _Kamisato_Ayaka_ @ 2022-05-04 09:52:05

@快斗游鹿 谢谢大佬！