38pts求救
查看原帖
38pts求救
1178681
hjbh楼主2024/5/19 06:42

rt

#include<bits/stdc++.h>
using namespace std;
struct node{
   int x,y,sum;
};
struct zm{
   int x,y;
   char c;
}z[60]; 
queue <node> q; 
int n,m,vis[1145][1145],s[1145][1145],nx[4][4]={{1,0},{0,1},{-1,0},{0,-1}},zb[27],sx,sy,ex,ey,idx;
char a[1145][1145];
int main(){
   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;
   			s[i][j]=0;
   			sx=i,sy=j;
   			node temp={i,j,0};
   			q.push(temp); 
   		}
   		if(a[i][j]<='Z'&&a[i][j]>='A'){
   			idx++;
   			z[idx].x=i,z[idx].y=j,z[idx].c=a[i][j];
   		}
   		if(a[i][j]=='='){
   			ex=i,ey=j;
   		}
   	}
   }
   while(!q.empty()){
   	//cout<<q.front().x<<" "<<q.front().y<<endl;
   	if(q.front().x==ex&&q.front().y==ey){
   		cout<<q.front().sum;
   		return 0;
   	}
   	for(int i=0;i<4;i++){
   		int tx=nx[i][0]+q.front().x,ty=nx[i][1]+q.front().y;
   		if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&!vis[tx][ty]&&a[tx][ty]!='#'){
   			vis[tx][ty]=1;
   			s[tx][ty]=q.front().sum+1;
   			node temp={tx,ty,q.front().sum+1};
   			q.push(temp);
   			if(a[tx][ty]>='A'&&a[tx][ty]<='Z' ){
   				for(int j=1;j<=idx;j++){
   					if(z[j].x==tx && z[j].y==ty) zb[j]=1; 
   					if(z[j].c==a[tx][ty] && zb[j]==0 && vis[z[j].x][z[j].y]==0){
   						zb[j]=1;
   						tx=z[j].x,ty=z[j].y;
   						vis[tx][ty]=1;
   						node tp={tx,ty,q.front().sum+1};
   						q.push(tp);
   					}
   				}
   			} 
   		}
   	} 
   	q.pop();
   }
   cout<<s[ex][ey];
}
2024/5/19 06:42
加载中...