90pts WA on test6 求助

Little_Zyl @ 2024-06-06 13:43:58

#include<bits/stdc++.h>
using namespace std;
const int inf=(1<<31)-1;
int n,qx,qy,zx,zy,dis[1000005],bj[1000005];
vector<pair<int,int> > G[10005];
char sz[1005][1005];
queue<int> q;
void spfa(int s){
    for(int i=1;i<=n*n;i++)dis[i]=inf;
    dis[s]=0;
    q.push(s);
    while(q.size()){
        int u=q.front();
        bj[u]=0;
        q.pop();
        for(auto e:G[u]){
            int v=e.first,cost=e.second;
            if(dis[u]+cost<dis[v]){
                dis[v]=dis[u]+cost;
                if(bj[v]==0){
                    bj[v]=1;
                    q.push(v);
                }
            }
        }
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            cin>>sz[i][j];
            if(sz[i][j]=='A')qx=i,qy=j;
            if(sz[i][j]=='B')zx=i,zy=j;
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            if(sz[i][j]=='x')continue;
            for(int k=j-1;k>=1;k--){
                if(sz[i][k]=='x')break;
                G[i*n-n+j].push_back({i*n-n+k,1});
            }
            for(int k=j+1;k<=n;k++){
                if(sz[i][k]=='x')break;
                G[i*n-n+j].push_back({i*n-n+k,1});
            }
            for(int k=i-1;k>=1;k--){
                if(sz[k][j]=='x')break;
                G[i*n-n+j].push_back({k*n-n+j,1});
            }
            for(int k=i+1;k<=n;k++){
                if(sz[k][j]=='x')break;
                G[i*n-n+j].push_back({k*n-n+j,1});
            }
        }
    spfa(qx*n+qy-n);
    cout<<dis[zx*n-n+zy]-1;
    return 0;
}

by Delete_error @ 2024-06-06 22:42:04

//test
#include<bits/stdc++.h>
using namespace std;
const int inf=(1<<31)-1;
int n,qx,qy,zx,zy,dis[1000005],bj[1000005];
vector<pair<int,int> > G[10005];
char sz[1005][1005];
queue<int> q;
void spfa(int s){
    for(int i=1;i<=n*n;i++)dis[i]=inf;
    dis[s]=0;
    q.push(s);
    while(q.size()){
        int u=q.front();
        bj[u]=0;
        q.pop();
        for(auto e:G[u]){
            int v=e.first,cost=e.second;
            if(dis[u]+cost<dis[v]){
                dis[v]=dis[u]+cost;
                if(bj[v]==0){
                    bj[v]=1;
                    q.push(v);
                }
            }
        }
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            cin>>sz[i][j];
            if(sz[i][j]=='A')qx=i,qy=j;
            if(sz[i][j]=='B')zx=i,zy=j;
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            if(sz[i][j]=='x')continue;
            for(int k=j-1;k>=1;k--){
                if(sz[i][k]=='x')break;
                G[i*n-n+j].push_back({i*n-n+k,1});
            }
            for(int k=j+1;k<=n;k++){
                if(sz[i][k]=='x')break;
                G[i*n-n+j].push_back({i*n-n+k,1});
            }
            for(int k=i-1;k>=1;k--){
                if(sz[k][j]=='x')break;
                G[i*n-n+j].push_back({k*n-n+j,1});
            }
            for(int k=i+1;k<=n;k++){
                if(sz[k][j]=='x')break;
                G[i*n-n+j].push_back({k*n-n+j,1});
            }
        }
    spfa(qx*n+qy-n);
    if(dis[zx*n-n+zy]==inf) cout<<-1;
    else cout<<dis[zx*n-n+zy]-1;
    return 0;
}

by Delete_error @ 2024-06-06 22:42:40

没输出-1啊啊QAQ 求关