第4点WA,BFS
查看原帖
第4点WA,BFS
779997
like_tis楼主2024/8/1 20:43
#include<bits/stdc++.h>
using namespace std;
struct node{
    pair<int,int> x;
    int step;
    bool CS;
};
int n,m,ans=INT_MAX,dx[]={0,1,0,-1},dy[]={1,0,-1,0};
char a[305][305];
pair<int,int> s,e;
pair<pair<int,int>,pair<int,int> > cs[30];
bool have[30],vis[305][305];
bool operator== (pair<int,int> x,pair<int,int> y){
    return x.first==y.first&&x.second==y.second;
}
char A(pair<int,int> x){
    return a[x.first][x.second];
}
void bfs(){
    queue<node> q;
    vis[s.first][s.second]=true;
    q.push({s,0,false});
    while(q.size()){
        pair<int,int> x=q.front().x;
        int step=q.front().step;
        bool CS=q.front().CS;
        q.pop();
        if(x==e){
            ans=min(ans,step);
            return;
        }
        if('A'<=A(x)&&A(x)<='Z'&&!CS){
            if(cs[A(x)-'A'].first==x) q.push({cs[A(x)-'A'].second,step,true});
            else q.push({cs[A(x)-'A'].first,step,true});
        }
        else{
            for(int i=0;i<4;i++){
                int nx=x.first+dx[i];
                int ny=x.second+dy[i];
                if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&!vis[nx][ny]&&a[nx][ny]!='#'){
                    vis[nx][ny]=true;
                    q.push({{nx,ny},step+1,false});
                }
            }
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%s",a[i]+1);
        for(int j=1;j<=m;j++){
            if(a[i][j]=='@') s={i,j};
            else if(a[i][j]=='=') e={i,j};
            else if('A'<=a[i][j]&&a[i][j]<='Z'){
                if(have[a[i][j]-'A']){
                    cs[a[i][j]-'A'].second.first=i;
                    cs[a[i][j]-'A'].second.second=j;
                }
                else{
                    cs[a[i][j]-'A'].first.first=i;
                    cs[a[i][j]-'A'].first.second=j;
                    have[a[i][j]-'A']=true;
                }
            }
        }
    }
    bfs();
    printf("%d",ans);
    return 0;
}
2024/8/1 20:43
加载中...