70分 WA 5个点 求助大佬!!
查看原帖
70分 WA 5个点 求助大佬!!
1093443
wxgmjfhy楼主2023/10/19 00:15
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define int long long
char a[305][305];
int f[305][305];
//标记走过以及不能走的点
int n,m;
int xx[4]={0,0,1,-1};
int yy[4]={1,-1,0,0};
//玉米 # 这些格子是不可以通过的。
//草地 . 可以简单的通过。
//传送装置 每一对大写字母A-A,B-B...
//出口=   起点 @
map<char,vector<pair<int,int>>>mp;
//传送器
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    int x,y;
    for(int i=0;i<n;i++){
        for(int t=0;t<m;t++){
            cin>>a[i][t];
            if(a[i][t]=='@')x=i,y=t;
            else if(a[i][t]>='A'&&a[i][t]<='Z'){
                mp[a[i][t]].push_back({i,t});
            }else if(a[i][t]=='#')f[i][t]=1;
        }
    }
    int cnt=0;
    int ans=0x7fffffff;
    queue<pair<pair<int,int>,int>>q;
    q.push({{x,y},cnt});
    while(!q.empty()){
        x=q.front().ff.ff,y=q.front().ff.ss,cnt=q.front().ss;
        q.pop();
        if(a[x][y]=='='){
            //cout<<cnt;
            //return 0;
            ans=min(ans,cnt);
            f[x][y]=0;
            continue;
        }
        if(a[x][y]>='A'&&a[x][y]<='Z'){
            //f[x][y]=0;
            for(auto w:mp[a[x][y]]){
                if(w.ff==x)continue;
                x=w.ff,y=w.ss;
                //f[x][y]=1;
                break;
            }
        }
        for(int i=0;i<4;i++){
            int xa=x+xx[i],ya=y+yy[i];
            if(xa>=0&&xa<n&&ya>=0&&ya<m&&!f[xa][ya]){
                f[xa][ya]=1;
                q.push({{xa,ya},cnt+1});
            }
        }
    }
    cout<<ans;
    return 0;
}
2023/10/19 00:15
加载中...