MnZn求助,悬赏关注
查看原帖
MnZn求助,悬赏关注
633466
LiaoYF1楼主2022/11/16 20:17
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int n,m,sx,sy,ex,ey,dis[305][305];
const int dx[4]={1,0,0,-1},
          dy[4]={0,1,-1,0};
char a[305][305];
queue<int> qx,qy;
int main(){
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);
    memset(dis,-1,sizeof(dis));
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            if(a[i][j]=='@'){
                sx=i,sy=j;
            }else if(a[i][j]=='='){
                ex=i,ey=j;
            }
        }
    }
    qx.push(sx),qy.push(sy);
    dis[sx][sy]=0;
    while(!qx.empty()){
        int x=qx.front(),y=qy.front();
        qx.pop(),qy.pop();
        if(x==ex&&y==ey)break;
        for(int i=0;i<4;i++){
            int nx=x+dx[i],ny=y+dy[i];
            if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&dis[nx][ny]==-1){
                if(isupper(a[nx][ny])){
                    for(int j=1;j<=n;j++){
                        for(int k=1;k<=m;k++){
                            if(a[j][k]==a[nx][ny]&&(nx!=j||ny!=k)){
                                qx.push(j),qy.push(k);
                                dis[j][k]=dis[x][y]+1;
                            }
                        }
                    }
                }else if(a[nx][ny]!='#'){
                    qx.push(nx),qy.push(ny);
                    dis[nx][ny]=dis[x][y]+1;
                }
            }
        }
    }
    cout<<dis[ex][ey];
    return 0;
}

record 45分,WA+TLE#3

2022/11/16 20:17
加载中...