传送门怎么标记
查看原帖
传送门怎么标记
785704
jiawenbo楼主2024/5/3 17:13
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll book[301][301];
char A[301][301];
struct node
{
	ll x,y,step;
};
queue <node> Q;
ll nextn[5][3] = {{0,0,0},{0,0,1},{0,1,0},{0,0,-1},{0,-1,0}};
ll nextx[301],nexty[301];
map <char,pair<ll,ll>> mp;
int main()
{
	ll n,m,sx,sy,fx,fy;
	scanf("%lld%lld",&n,&m);
	for (ll i = 1; i <= n; i ++)
	{
		for (ll j = 1; j <= m; j ++)
		{
			scanf(" %c",&A[i][j]);
			if (A[i][j] == '@') sx = i,sy = j;
			if (A[i][j] == '=') fx = i,fy = j;
			if (A[i][j] >= 'A' && A[i][j] <= 'Z')
			{
				for (ll i1 = 1; i1 <= n; i1 ++)
				{
					for (ll j1 = 1; j1 <= m; j1 ++)
					{
						if (A[i1][j1] == A[i][j] && (i1 != i || j1 != j))
						{
							nextx[i1] = i;
							nexty[j1] = j;
							nextx[i] = i1;
							nexty[j] = j1;
						}
					}
				}
			}
		}
	}
	Q.push((node){sx,sy,0});
	book[sx][sy] = 1;
	while (Q.size())
	{
		ll tx,ty;
		for (ll i = 1; i <= 4; i ++)
		{
			tx = Q.front().x + nextn[i][1];
			ty = Q.front().y + nextn[i][2];
			if (tx < 1 || tx > n || ty < 1 || ty > m) continue;
			if (A[tx][ty] != '#' && !book[tx][ty])//这里涉及到了传送门怎么标记
			{
				if (nextx[tx] && nexty[ty]) Q.push((node){nextx[tx],nexty[ty],Q.front().step + 1});
				else Q.push((node){tx,ty,Q.front().step + 1}),book[tx][ty] = 1;
			}
			if (tx == fx && ty == fy)
			{
				printf("%lld",Q.back().step);
				return 0;
			}
		}
		Q.pop();
	}
	return 0;
}
2024/5/3 17:13
加载中...