【非题解】使用map的较快速解法
查看原帖
【非题解】使用map的较快速解法
562521
junhaowang楼主2024/8/4 15:09

供参考。

大坑:传送门不能不传送!

/*
我是史上最怪C++代码格式的传承人
括号前总有空格
定义变量像函数
花括号单独一行
此格式濒临失传
*/
#include <bits/stdc++.h>
//#pragma GCC optimize(2)
using namespace std;

#define int long long
#define rint register int
#define endl '\n'
#define debug(x) cerr << #x << '=' << x << endl;

int n, m, sx, sy, ex, ey, ans = 0x3f3f3f3f3f3f3f3f,
	go[4][2] = {-1, 0, 0, 1, 1, 0, 0, -1};
bool mp[305][305], vis[305][305];
char tmp;

//呃……难道我真的是map狂魔?
map <pair <int, int>, pair <int, int> > doormp;
unordered_map <char, pair <int, int> > previousmp;
unordered_map <char, bool> used;
map <pair <int, int>, bool> able;

queue <tuple <int, int, int> > que;

bool judge(int x, int y)
{
	return x >= 1 && x <= n && y >= 1 && y <= m && mp[x][y] && !vis[x][y];
}

void bfs(void)
{
	vis[sx][sy] = true;
	que.push(make_tuple(sx, sy, 0));
	while (!que.empty())
	{
		auto fr = que.front();
		que.pop();
		if (get <0> (fr) == ex && get <1> (fr) == ey)
		{
			cout << get <2> (fr);
			return ;
		}
		//警告:必须注意传送门强制传送不可选择!!!
		if (able[make_pair(get <0> (fr), get <1> (fr))])
		{
			auto [xx, yy] = doormp[make_pair(get <0> (fr), get <1> (fr))];
			auto tmp = make_tuple(xx, yy, get <2> (fr));
			fr = tmp;
		}
		for (rint i = 0; i < 4; i++)
		{
			auto [xx, yy, st] = fr;
			xx += go[i][0], yy += go[i][1];
			if (judge(xx, yy))
			{
				vis[xx][yy] = true;
				que.push(make_tuple(xx, yy, st + 1));
			}
		}
	}
	return ;
}

signed main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (rint i = 1; i <= n; i++)
	{
		for (rint j = 1; j <= m; j++)
		{
			cin >> tmp;
			switch (tmp)
			{
				case '#':
					mp[i][j] = false;
					break;
				case '.':
					mp[i][j] = true;
					break;
				case '=':
					mp[i][j] = true;
					ex = i, ey = j;
					break;
				case '@':
					mp[i][j] = true;
					sx = i, sy = j;
					break;
				default:
					mp[i][j] = true;
					if (used[tmp])
					{
						doormp[previousmp[tmp]] = make_pair(i, j);
						doormp[make_pair(i, j)] = previousmp[tmp];
						able[make_pair(i, j)] = able[previousmp[tmp]] = true;
					}
					else
					{
						used[tmp] = true;
						previousmp[tmp] = make_pair(i, j);
					}
			}
		}
	}
	bfs();
	return 0;
}
2024/8/4 15:09
加载中...