题目链接
题目描述
给定一个 $n$ 行 $m$ 列的矩阵，矩阵中可能有三种字符：
#表示墙，不能移动到墙上。.表示可以行走的空地。- 英文大写字母表示传送门的序号，传送门成对出现，每个字母若出现，则仅出现两次。
玩家每秒可以向上、下、左、右移动一格，不能移动到墙上，也不能呆在原地不动。
在行走过程中，玩家如果走到了传送门上，无法选择是否传送，必然在一瞬间被传送到另一个与其配对的传送门处。
设两个配对的传送门 $A$ 分别为 $A_1$ 和 $A_2$，则当玩家踏入 $A_1$ 的瞬间，就会被传送到 $A_2$ 处，这个过程不消耗时间。但在传送到 $A_2$ 后，$A_2$ 传送门会失效一秒钟，不能直接回到传送门 $A_1$.
每次游戏，玩家出生在 $(1, 1)$，需要到达终点 $(n, m)$，求最少花费时间。
$1\leq n, m\leq 100$.
题目解释
例如下面的地图：
.#.
A#A
.#.
玩家从 $(1, 1)$ 走到 $(3, 1)$ 的其中一种合法方案为：
(1, 1)\rightarrow (2, 1)\rightarrow(2, 3)\rightarrow(1, 3)\rightarrow(2, 3)\rightarrow(2, 1)\rightarrow(3, 1)
$$
而这是一种不合法的方案：
(1, 1)\rightarrow(2, 1)\rightarrow(3, 1)
$$
因为碰到传送门必定被传送走。
题目分析
不难想到最短路，考虑如何建图。
要特殊处理的地方是：穿过传送门后的一秒。在这一秒，不能走回原来的传送门，只能走向其他点，而下一秒还可以再回来。
想到建立分层图对传送门进行处理。将传送门节点复制一份，放到第二层。此时第一层的传送门节点，代表的是还未被传送走的状态，而第二层的传送门节点，代表被传送到这个传送门之后的状态。
建图方式：
所以，与传送门相邻的节点可以到达第一层，但不能到达第二层；第一层的传送门节点不能到达与其相邻的节点（因为一定会被传走），而第二层的传送门节点可以到达与其相邻的节点。若同一层的两个传送门之间不相邻，则互相不可到达。
形式化地：
不妨设一对传送门分别为 $A_1$ 和 $A_2$，将所有传送门节点复制到第二层，复制后的节点叫 $B_1$ 和 $B_2$，传送门 $A_1$ 与空节点 $x$ 相邻。则：
传送门之间连边的方式为 $A_1\rightarrow B_2$，$A_2\rightarrow B_1$.
传送门与相邻节点之间连边的方式为：$x\rightarrow A_1$，$B_1\rightarrow x$.
这样建图之后，点数为最多为 $n^2+26\times 2$，边数也大概在 $n^2$ 量级。这样用堆优化的 Dijkstra 求出最短路即可。
代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 108;
int n, m;
char in[MAXN][MAXN];
int get(int x, int y) {//对坐标(x, y)做hash
return (x - 1) * m + y;
}
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
struct Edge{
int to, nxt, val;
}edge[(MAXN * MAXN) << 4];
int head[(MAXN * MAXN) << 1], e_cnt = 0;
void add(int u, int v, int w) {
edge[++e_cnt].to = v;
edge[e_cnt].val = w;
edge[e_cnt].nxt = head[u];
head[u] = e_cnt;
}
pair<int, int> door[30][2];
//door[i][0]存储的是，第i组传送门的第一个点的坐标，door[i][1]是第二个点的坐标
int dis[(MAXN * MAXN) << 1];
bool vis[(MAXN * MAXN) << 1];
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
void Dijkstra() {
memset(dis, 0x3f, sizeof(dis));
dis[1] = 0;
q.push(make_pair(0, 1));
while(!q.empty()) {
int id = q.top().second; q.pop();
if(vis[id]) continue;
vis[id] = true;
for(int i = head[id]; i; i = edge[i].nxt) {
int ne = edge[i].to, val = edge[i].val;
if(dis[ne] > dis[id] + val) {
dis[ne] = dis[id] + val;
q.push(make_pair(dis[ne], ne));
}
}
}
}
signed main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) {
cin >> (in[i] + 1);
}
//处理传送门：
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(in[i][j] >= 'A' && in[i][j] <= 'Z') {
int num = in[i][j] - 'A' + 1;
if(door[num][0].first == 0) {//第一次遇到
door[num][0] = make_pair(i, j);
} else {//第二次遇到，传送点之间跨层连边，即A1向B2连边，A2向B1连边
add(get(i, j), get(door[num][0].first, door[num][0].second) + n * m, 0);
add(get(door[num][0].first, door[num][0].second), get(i, j) + n * m, 0);
}
}
}
}
//处理空白点相关：
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(in[i][j] == '#') continue;
else if(in[i][j] == '.') {//对于空白点，可以向相邻的，第一层传送门/空白点连边
for(int k = 0; k < 4; k++) {
int nx = i + dir[k][0], ny = j + dir[k][1];
if(nx < 1 || nx > n || ny < 1 || ny > m) continue;
if(in[nx][ny] == '.') add(get(i, j), get(nx, ny), 1);
else if(in[nx][ny] != '#') {
add(get(i, j), get(nx, ny), 1);
}
}
} else {//对于传送门点，将第二层的传送门点向第一层相邻所有能走到的点连边
for(int k = 0; k < 4; k++) {
int nx = i + dir[k][0], ny = j + dir[k][1];
if(nx < 1 || nx > n || ny < 1 || ny > m) continue;
if(in[nx][ny] != '#') {
add(get(i, j) + n * m, get(nx, ny), 1);
}
}
}
}
}
Dijkstra();
if(dis[get(n, m)] >= 0x3f3f3f3f && dis[get(n, m) + n * m] >= 0x3f3f3f3f)//无法到达
cout << "Game Over." << endl;
else cout << min(dis[get(n, m)], dis[get(n, m) + n * m]) << endl;
return 0;
}