57求解
查看原帖
57求解
741299
zhangshibo678楼主2022/8/20 16:33
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
char a[1009][1009];
queue<pair<int,int> >q;
long long dis[1009][1009];
long long n,m,x2,y2,vis[1009][1009];
int fx[5]={0,-1,0,1,0},fy[5]={0,0,1,0,-1};
long long ans=0;
void go(int &x,int &y){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]==a[x][y]&&(x!=i||y!=j)){
			  x=i;y=j;
			  return ;
			}
		}
	}
}
int main(){
	long long tx,ty;
   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]=='='){
			tx=i;
			ty=j;
		}
}
}
   while(!q.empty()){
  	pair<int,int>t=q.front(); q.pop();
  		int nx=t.first;
		int ny=t.second;
		bool flag=0;//是否用过传送门
		int mx,my; 
		if(a[nx][ny]>='A'&&a[nx][ny]<='Z')//传送门 
		{
			mx=nx;
		    my=ny;
			go(nx,ny);
			flag=1;
		}
  	for(int i=1;i<=4;i++){
  		
  			int x=nx+fx[i];
  			int y=ny+fy[i];
  			
  			if(x<1||x>n||y<1||y>n||a[x][y]=='#'||vis[x][y])  continue;
  			
  			vis[x][y]=1;
  			if(!flag) dis[x][y]=dis[nx][ny]+1;
  			else dis[x][y]=dis[mx][my]+1;
  			
  			 q.push(make_pair(x,y));	
  	}
  }
  cout<<dis[tx][ty]<<endl;
	return 0;
}
2022/8/20 16:33
加载中...