哭了,38分
查看原帖
哭了,38分
504456
limoalin楼主2022/8/11 18:49
#include<iostream>
#include<cstring>
#include<queue>
#include<map>
using namespace std;
struct dian{
	int x1,y1;
}h;
queue<dian>q;
int n,m,sx,sy,fx,fy;
char c[310][310];
int v[27][5],g[310][310];
int dir[4][2]={0,1,1,0,-1,0,0,-1};
void bfs(){
	while(!q.empty()){
		dian t;
		t.x1=q.front().x1;t.y1=q.front().y1;
		q.pop();
		int x=t.x1,y=t.y1;
		for(int i=0;i<4;i++){
			int xx=x+dir[i][0],yy=y+dir[i][1];
			dian k;
			k.x1=xx;k.y1=yy;
			if(xx<1||xx>n||yy<1||yy>m||c[xx][yy]=='#'||(g[xx][yy]&&!(c[xx][yy]>='A'&&c[xx][yy]<='Z')))continue;
			if(g[xx][yy]==0)g[xx][yy]=g[x][y]+1;
			if(c[xx][yy]=='='){cout<<g[fx][fy];exit(0);}
			if(c[xx][yy]=='.')q.push(k);
			if(c[xx][yy]>='A'&&c[xx][yy]<='Z'){
				q.push(k);
				dian l;
				if(v[c[xx][yy]-'A'][1]==xx){l.x1=v[c[xx][yy]-'A'][3];l.y1=v[c[xx][yy]-'A'][4];}
				else{l.x1=v[c[xx][yy]-'A'][1];l.y1=v[c[xx][yy]-'A'][2];}
				q.push(l);g[l.x1][l.y1]=g[xx][yy];
			}
		}
	}
}
int main(){
	memset(c,'#',sizeof(c));
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			cin>>c[i][j];
			if(c[i][j]=='@'){sx=i;sy=j;}
			if(c[i][j]=='='){fx=i;fy=j;}
			if(c[i][j]>='A'&&c[i][j]<='Z')
			{if(v[c[i][j]-'A'][1]){v[c[i][j]-'A'][3]=i;v[c[i][j]-'A'][4]=j;}
		     else{v[c[i][j]-'A'][1]=i;v[c[i][j]-'A'][2]=j;}}
		}
	h.x1=sx;h.y1=sy;
	g[sx][sy]=0;
	q.push(h);
	bfs();
}
2022/8/11 18:49
加载中...