ABC436D
XXh0919
·
·
题解
沉痛悼念南京大屠杀死难者。
## 前言
民族血脉觉醒的我场切 A~F，于是写这篇题解以作纪念。
## 题意
有一个 $n\times m$ 的迷宫，一个人要从 $(1,1)$ 走到 $(n,m)$。其中有些格子是普通格子（`.`），有些格子是障碍物（`#`），有些是传送门（`a`~`z`）。这个人有两种行动方式：
1. 从当前格子沿四个方向（上、下、左、右）之一移动到一个格子之外的格子，但不能移动到障碍物格子或迷宫外。
2. 如果这个人在写有英文小写字母的格子上，则 TA 可以传送到写有相同字母的单元格上。
每种方式每一次花费 $1$ 的时间。
请判断是否可以从 $(1,1)$ 移动到 $(n,m)$，如果可以，找出所需的最少总操作次数，否则输出 $-1$。
$1\le n,m\le1000$。
## 解法
### 1.BFS
首先我们看没有传送门该怎么做。其实这种就是普通的 bfs，只需要从当前格子往上下左右进行扩展，最后扩展到 $(n,m)$。
但现在有了传送门。那么我们是不是可以特判一手，如果当前所处格子写有字母，我们就到写有相同字母的格子里去搜，如果说搜到一个格子所花费时间更短，就更新答案，并把这个格子加入队列。然后一直扩展到 $(n,m)$ 就结束。
::::info[Code]
```cpp
#include <bits/stdc++.h>
#define loop(i,a,b) for(int i=(a);~i;i=(b))
#define Mem(a,b) memset ((a),(b),sizeof((a)))
#define eb emplace_back
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
constexpr int N = 2e5 + 15;
namespace FAST_IO {
//快读快写已为您省略
}
using namespace FAST_IO;
int n, m;
char s[2000][2000];
bool vis[2000][2000], used[30];
vector <pair <int, int>> w[30];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
ll dis[2000][2000];
ll bfs () {
Mem (dis, 0x3f);
queue <pair <int, int>> q;
dis[1][1] = 0;
vis[1][1] = true;
q.push ({1, 1});
while (!q.empty ()) {
int x, y;
tie (x, y) = q.front ();
q.pop ();
if (x == n && y == m) return dis[x][y];
for (int i = 0; i < 4; ++ i) {
int xx = x + dx[i], yy = dy[i] + y;
if (s[xx][yy] == '#' || xx < 1 || xx > n || yy < 1 || yy > m || vis[xx][yy]) continue;
vis[xx][yy] = true;
if (dis[xx][yy] > dis[x][y] + 1) {
dis[xx][yy] = dis[x][y] + 1;
q.push ({xx, yy});
}
}
if (isalpha (s[x][y])) {
int c = s[x][y] - 'a';
if (used[c]) continue;
used[c] = true;
int a, b;
for (auto p : w[c]) {
tie (a, b) = p;
if (dis[a][b] > dis[x][y] + 1) {
dis[a][b] = dis[x][y] + 1;
q.push ({a, b});
}
}
}
}
return -1ll;
}
int main () {
read (n, m);
for (int i = 1; i <= n; ++ i) read (s[i] + 1);
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= m; ++ j) {
if (s[i][j] >= 'a' && s[i][j] <= 'z') {
w[s[i][j] - 'a'].eb (i, j);
}
}
}
print (bfs (), '\n');
return 0;
}
```
::::
时间复杂度 $O(nm)$，[AC 记录](https://atcoder.jp/contests/abc436/submissions/71674029)。
### 2.最短路
看到了网格图，作为一个网络流资深（？）老玩家，肯定会想到将其变成一个图进行求解。那么怎么建图呢？首先我们把传送门当成普通格子处理，向每一个格子的上下左右的格子各连一条边，边数是 $O(nm)$。然后就是传送门。显然如果我们每两个传送门之间建一条边，复杂度是接受不了的。所以我们可以开一个虚拟节点，让这个虚拟节点连向这些能互相到达的传送门，就能将边数降到 $O(1)$ 级别，复杂度也就可以接受了。
最后跑一个 Dijkstra 就没了。
::::info[Code]
```cpp
#include <bits/stdc++.h>
#define loop(i,a,b) for(int i=(a);~i;i=(b))
#define Mem(a,b) memset ((a),(b),sizeof((a)))
#define eb emplace_back
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
constexpr int N = 3e6 + 15;
namespace FAST_IO {
//快读快写已为您省略
}
using namespace FAST_IO;
int n, m;
char s[2000][2000];
int head[N], to[N << 1], val[N << 1], nxt[N << 1], idx;
ll dis[N];
bool vis[N];
struct node {
ll dis;
int u;
bool operator <(const node &x) const {
return dis > x.dis;
}
};
priority_queue <node> q;
int id[2000][2000], cnt;
vector <int> w[28];
void add (int u, int v, int w) {
to[idx] = v;
val[idx] = w;
nxt[idx] = head[u];
head[u] = idx ++;
}
void Dijkstra (int s) {
Mem (dis, 0x3f);
dis[s] = 0;
q.push ({0, s});
while (!q.empty ()) {
int u = q.top().u;
q.pop ();
if (vis[u]) continue;
vis[u] = true;
loop (i, head[u], nxt[i]) {
int v = to[i], w = val[i];
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
q.push ({dis[v], v});
}
}
}
}
int main () {
Mem (head, -1);
read (n, m);
for (int i = 1; i <= n; ++ i) read (s[i] + 1);
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= m; ++ j) {
id[i][j] = ++ cnt;
}
}
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= m; ++ j) {
if (s[i][j] == '#') continue;
if (s[i + 1][j] != '#' && i + 1 <= n) add (id[i][j], id[i + 1][j], 1);
if (s[i - 1][j] != '#' && i - 1 >= 1) add (id[i][j], id[i - 1][j], 1);
if (s[i][j + 1] != '#' && j + 1 <= m) add (id[i][j], id[i][j + 1], 1);
if (s[i][j - 1] != '#' && j - 1 >= 1) add (id[i][j], id[i][j - 1], 1);
if (isalpha (s[i][j])) w[s[i][j] - 'a'].eb (id[i][j]);
}
}
for (int c = 0; c < 26; ++ c) {
if (w[c].empty()) continue;
int vir = ++ cnt;
for (int u : w[c]) {
add(u, vir, 0);
add(vir, u, 1);
}
}
Dijkstra (1);
if (dis[n * m] == 0x3f3f3f3f3f3f3f3f) dis[n * m] = -1;
print (dis[n * m], '\n');
return 0;
}
```
::::
时间复杂度 $O(nm\log nm)$，虽然复杂度更劣，但至少也是一种解法对吧，[AC 记录](https://atcoder.jp/contests/abc436/submissions/71713289)。