39分 大佬求解
查看原帖
39分 大佬求解
741299
zhangshibo678楼主2022/8/20 07:56
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
char a[1009][1009];
queue<pair<int,int> >q;
int dis[1009][1009];
int n,m,x2,y2,vis[1009][1009];
int fx[5]={0,-1,0,1,0},fy[5]={0,0,1,0,-1};
int ans=0;
void go(int x,int y,char r){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]==r&&(x!=i||y!=j)){
				q.push(make_pair(i,j));
				vis[i][j]=1;
				dis[i][j]=dis[x][y];
			}
		}
	}
}
int main(){
	if(!q.empty()) q.pop();
   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]=='@'){
   		  	vis[i][j]=1;
  q.push(make_pair(i,j)); 
   	}
    if(a[i][j]=='='){
    	x2=i,y2=j;
    }
}
}
   while(!q.empty()){
  	pair<int,int>t=q.front(); q.pop();
  	for(int i=1;i<=4;i++){;
  			int x=t.first+fx[i];
  			int y=t.second+fy[i];
  			if(x<1||x>n||y<1||y>n||a[x][y]=='#'||vis[x][y]==1) continue;
       
  			vis[x][y]=1;
			  dis[x][y] = dis[t.first][t.second]+1;
  			if(a[x][y]>='A'&&a[x][y]<='Z')  go(x,y,a[x][y]);
  			else  q.push(make_pair(x,y));
  	}
  }
cout<<dis[x2][y2]<<endl;
	return 0;
}
2022/8/20 07:56
加载中...