79分求助
查看原帖
79分求助
1101962
xiao12chen楼主2024/5/23 19:30
#include<iostream>
#include<cstring>
#include<queue>
#include<map>
using namespace std;
int n,m;
char a[400][400];
queue<pair<int,int> >q;
struct node{
	int x1,y1;
	int x2,y2;
}b[30];
int vis[400][400];
int ans[400][400];
int sx,sy,ex,ey;
int nx[5]={0,0,1,-1};
int ny[5]={1,-1,0,0};
void bfs(){
	vis[sx][sy]=1;
	q.push(make_pair(sx,sy));
	while(!q.empty()){
		int x=q.front().first;
		int y=q.front().second;
		for(int i=0;i<4;i++){
		//	cerr<<q.front().first<<" "<<q.front().second<<" "<<ans[q.front().first][q.front().second]<<endl;
			int xx=nx[i]+x;
			int yy=ny[i]+y;
			if(xx>0&&yy>0&&xx<=n&&yy<=m&&a[xx][yy]!='#'&&vis[xx][yy]==0){
				if(ans[xx][yy]==0||a[xx][yy]>='A'&&a[xx][yy]<='Z')
				ans[xx][yy]=ans[q.front().first][q.front().second]+1;
				else
				ans[xx][yy]=min(ans[q.front().first][q.front().second]+1,ans[xx][yy]);
				if(a[xx][yy]>='A'&&a[xx][yy]<='Z'){
					vis[xx][yy]++;
					int xxx=a[xx][yy]-'A';
					if(b[xxx].x1==xx){q.push(make_pair(b[xxx].x2,b[xxx].y2));
						//if(ans[b[xxx].x2][b[xxx].y2]==0)
						ans[b[xxx].x2][b[xxx].y2]=ans[xx][yy];
						//else 
						//ans[b[xxx].x2][b[xxx].y2]=min(ans[b[xxx].x2][b[xxx].y2],ans[xx][yy]);
					}else{q.push(make_pair(b[xxx].x1,b[xxx].y1));
						//if(ans[b[xxx].x1][b[xxx].y1]==0){
							ans[b[xxx].x1][b[xxx].y1]=ans[xx][yy];
						//}
						//else 
						//ans[b[xxx].x1][b[xxx].y1]=min(ans[b[xxx].x1][b[xxx].y1],ans[xx][yy]);
					}
				}
				else {
					vis[xx][yy]=1;
					q.push(make_pair(xx,yy));
				}
			}
		}q.pop();
	}
}
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]>='A'&&a[i][j]<='Z'){
				if(b[a[i][j]-'A'].x1==0){
					b[a[i][j]-'A'].x1=i;
					b[a[i][j]-'A'].y1=j;
				}else{
					b[a[i][j]-'A'].x2=i;
					b[a[i][j]-'A'].y2=j;
				}
			}if(a[i][j]=='@'){
				sx=i;
				sy=j;
			}if(a[i][j]=='='){
				ex=i;
				ey=j;
			}
		}
	}bfs();
	cout<<ans[ex][ey];
	return 0;
}
2024/5/23 19:30
加载中...