58求助
查看原帖
58求助
490978
小超手123楼主2022/1/29 12:34
#include<bits/stdc++.h>
using namespace std;
int n,m,sx,sy;
char a[310][310];
int c[30][6];
bool vis[310][310];
int walk[5][3]={{1,0},{0,1},{-1,0},{0,-1}};
struct node
{
	int x,y,d;
};
queue<node>Q;
int bfs()
{
	vis[sx][sy]=1;
	Q.push((node){sx,sy,0});
	while(!Q.empty())
	{
		node cmp=Q.front();
		int xx=cmp.x,yy=cmp.y,dd=cmp.d;
		Q.pop();
		for(int i=0;i<4;i++)
		{
			int dx=xx+walk[i][0],dy=yy+walk[i][1];
			if(dx>=1&&dx<=n&&dy>=1&&dy<=m&&a[dx][dy]!='#'&&vis[dx][dy]==0)
			{
				vis[dx][dy]=1;
				if(a[dx][dy]>='A'&&a[dx][dy]<='Z')
				{
					int u=a[dx][dy]-'A'+1;
					if(dx==c[u][1]&&dy==c[u][2])
					{
						dx=c[u][3];
						dy=c[u][4];
					}
					else
					{
						dx=c[u][1];
						dy=c[u][2];
					}
				}
				Q.push((node){dx,dy,dd+1});
				vis[dx][dy]=1;
				if(a[dx][dy]=='=')
				{
					return dd+1;
				}
			}
		}
	}
}
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')
			{
				int x=a[i][j]-'A'+1;
				if(c[x][1]==0)
				{
					c[x][1]=i;
					c[x][2]=j;
				}
				else
				{
					c[x][3]=i;
					c[x][4]=j;
				}
			}
			if(a[i][j]=='@')
			{
				sx=i;
				sy=j;
			}
		}
	}
	cout<<bfs();
    return 0; 
}
2022/1/29 12:34
加载中...