86pts玄关!
查看原帖
86pts玄关!
999658
talkwithcpp楼主2024/8/30 20:41
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
const int INF = 0x7fffffff;

int n, m, aans = INF;
char map[500][500];
pair<int, int> chu[30][2];
int a, b, c, d;
bool vis[500][500];

int ans[500][500];

int dx[5] = { 0,1,0,-1,0 };
int dy[5] = { 0,0,1,0,-1 };

queue< pair<int, int> > q;

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
		{
			cin >> map[i][j];
			if ('A' <= map[i][j] && map[i][j] <= 'Z')
			{
				//vis[i][j] = -2;
				if (!chu[map[i][j] - 'A'][0].first) chu[map[i][j] - 'A'][0] = make_pair(i, j);
				else chu[map[i][j] - 'A'][1] = make_pair(i, j);
			}
			if (map[i][j] == '@') a = i, b = j;
			if (map[i][j] == '=') c = i, d = j;
		}

	vis[a][b] = 1;
	q.push(make_pair(a, b));
	while (!q.empty())
	{
		int x = q.front().first, y = q.front().second;
		q.pop();
		for (int i = 1; i <= 4; ++i)
		{
			int xx = x + dx[i], yy = y + dy[i];

			if (xx<1 || xx>n || yy<1 || xx>n || map[xx][yy] == '#' || vis[xx][yy]) continue;

			ans[xx][yy] = ans[x][y] + 1;
			vis[xx][yy] = 1;

			if (map[xx][yy] == '.')
			{
				q.push(make_pair(xx, yy));
			}
			if (map[xx][yy] == '=')
			{
				//for (int i = 1; i <= n; ++i)
				//{
				//	for (int j = 1; j <= m; ++j)
				//		cout << ans[i][j] << " ";
				//	cout << "\n";
				//}

				aans = min(ans[xx][yy], aans);
			}
			if ('A' <= map[xx][yy] && map[xx][yy] <= 'Z')
			{
				int e, f;
				if (chu[map[xx][yy] - 'A'][0].first == xx && chu[map[xx][yy] - 'A'][0].second == yy)
					e = chu[map[xx][yy] - 'A'][1].first, f = chu[map[xx][yy] - 'A'][1].second;
				else e = chu[map[xx][yy] - 'A'][0].first, f = chu[map[xx][yy] - 'A'][0].second;

				q.push(make_pair(e, f));
				ans[e][f] = ans[xx][yy];

				//vis[xx][yy] = 0;
			}
		}
	}
	
	cout << aans;
	return 0;
}
2024/8/30 20:41
加载中...