求助大佬!!BFS 58pts
查看原帖
求助大佬!!BFS 58pts
519384
Link_Cut_Y楼主2022/2/25 22:02
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <map> 

using namespace std;

typedef pair<int, int> PII;
const int N = 310;

struct Node
{
	PII a, b;
};

map<char, Node> Map; // 用map存一下每一个字母对(传送门)所对应的的起始点
int steps[N][N];
char g[N][N];
int n, m;
PII start, End;
bool st[N][N];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

void bfs()
{
	queue<PII> q;
	
	q.push(start);
	st[start.first][start.second] = true;
	
	while (q.size())
	{	
		auto t = q.front();
		q.pop();
		
		if (g[t.first][t.second] == '.' || g[t.first][t.second] == '@')
		{
//			printf("%d %d is a '.'\n", t.first, t.second);
			
			for (int i = 0; i < 4; i ++ )
			{
				int tx = t.first + dx[i], ty = t.second + dy[i];
				if (g[tx][ty] == '#') continue;
				if (st[tx][ty]) continue;
				st[tx][ty] = true;
				steps[tx][ty] = steps[t.first][t.second] + 1;
				q.push({tx, ty});
			}
		}
		
		else if (g[t.first][t.second] >= 'A' || g[t.first][t.second] <= 'Z')
		{
			Node d = Map[g[t.first][t.second]];
			if (d.a.first == t.first && d.a.second == t.second)
			{
				if (st[d.b.first][d.b.second])
				{
					for (int i = 0; i < 4; i ++ )
					{
						int tx = t.first + dx[i], ty = t.second + dy[i];
						if (g[tx][ty] == '#') continue;
						if (st[tx][ty]) continue;
						st[tx][ty] = true;
						steps[tx][ty] = steps[t.first][t.second] + 1;
						q.push({tx, ty});
					}
				}
				
				else
				{
					st[d.b.first][d.b.second] = true;
					steps[d.b.first][d.b.second] = steps[t.first][t.second];
					q.push({d.b.first, d.b.second});
				}
			}
			else if (d.b.first == t.first && d.b.second == t.second)
			{
				if (st[d.a.first][d.a.second])
				{
					for (int i = 0; i < 4; i ++ )
					{
						int tx = t.first + dx[i], ty = t.second + dy[i];
						if (g[tx][ty] == '#') continue;
						if (st[tx][ty]) continue;
						st[tx][ty] = true;
						steps[tx][ty] = steps[t.first][t.second] + 1;
						q.push({tx, ty});
					}
				}
				
				else
				{
					st[d.a.first][d.a.second] = true;
					steps[d.a.first][d.a.second] = steps[t.first][t.second];
					q.push({d.a.first, d.a.second});
				}
			}
		}
	}
}

int main()
{
	cin >> n >> m;
	
	for (int i = 1; i <= n; i ++ )
		scanf("%s", g[i] + 1);
		
	for (int i = 1; i <= n; i ++ )
		for (int j = 1; j <= m; j ++ )
			if (g[i][j] == '@') start = {i, j};
			else if (g[i][j] == '=') End = {i, j};
			else if (g[i][j] >= 'A' && g[i][j] <= 'Z')
			{
				if (Map[g[i][j]].a.first && Map[g[i][j]].a.second)
					Map[g[i][j]].b = {i, j};
				else Map[g[i][j]].a = {i, j};
			}
			
	bfs();
	
	/*
	printf("the start is:%d %d\n", start.first, start.second);
	printf("the end is:%d %d\n", End.first,End.second);
	*/
	
	/*
	for (int i = 1; i <= n; i ++ )
	{
		for (int j = 1; j <= m; j ++ )
			cout << steps[i][j] << ' ';
			
		cout << endl;
	}
	*/
	
	cout << steps[End.first][End.second] << endl;
	
	return 0;
}
2022/2/25 22:02
加载中...