72求调 WA 6,8, 9,10
查看原帖
72求调 WA 6,8, 9,10
858782
qwe962楼主2024/11/18 23:29
#include <bits/stdc++.h>

using namespace std;

int main() {
    int n,m;
    cin>>n>>m;
    cin.ignore();
    vector<string>a(n+5);
    int x0,y0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }

    for(int i=1;i<=n;i++){
        for(int j=0;j<=a[i].size();j++){
            if(a[i][j]=='@') x0=i,y0=j;
        }
    }

    vector<pair<int,int>>b={{1,0},{-1,0},{0,1},{0,-1}};

    queue<pair<int,int>>q;
    vector<vector<int>>step(n+5,vector<int>(m+5,0));
    q.push(make_pair(x0,y0));
    vector<vector<int>>v(n+5,vector<int>(m+5,0));
    v[x0][y0]=1;
    int out=INT_MAX;
    while(!q.empty()){
        int x=q.front().first,y=q.front().second;
        q.pop();
        for(int i=0;i<4;i++){

            int tx=b[i].first,ty=b[i].second;
            if(x+tx<1 || x+tx>n || y+ty<1 || y+ty>m) continue;

            if(a[x+tx][y+ty]=='.' && v[x+tx][y+ty]==0){
                q.push({x+tx,y+ty});
                v[x+tx][y+ty]=1;
                step[x+tx][y+ty]= step[x][y]+1;
            }
            else if(a[x+tx][y+ty]=='#' || a[x+tx][y+ty]=='@'){
                continue;
            }
            else if(a[x+tx][y+ty]=='='){
                out=min(out,step[x][y]+1);
            }
            else if(a[x+tx][y+ty]>='A' && a[x+tx][y+ty]<='Z' && v[x+tx][y+ty]<=1){
                char t=a[x+tx][y+ty];
                v[x+tx][y+ty]++;
                int w1,w2,flag=0;
                for(int k=1;k<=n && !flag;k++){
                    for(int l=1;l<=m;l++){
                        if(a[k][l]==t && (k!=x+tx || l!=y+ty)){
                            w1=k,w2=l,flag=1;
                            break;
                        }
                    }
                }
                if(flag==0) continue;
                q.push(make_pair(w1,w2));
                step[w1][w2]= step[x][y]+1;
            }
        }
    }
    cout<<out;
    return 0;
}
2024/11/18 23:29
加载中...