[yLOI2023] C 云梦谣
一扶苏一
·
·
题解
[yLOI2023] C 云梦谣
Description
给定一个 n \times m 的方格阵，每个格子有一个高度 h_{i,j}，或者是不能通行的障碍物。且有 k 个格子可以传送。每秒可以做如下三件事之一：
- 移动到相邻四联通的格子。
- 如果当前格子允许传送，则可以传送到任意别的允许传送的格子上，条件是目标格子和当前格子等高。
- 改变当前格子的高度为任意正整数。
求从 (1,1) 走到 (n,m) 的最短用时。
## Analysis
### 算法一
当 $n = m = 2$ 时有一万种方法求解，不表。可得 $20$ 分。
特别的，测试点 $1$ 输出 $-1$ 可得 $5$ 分。
### 算法二
当 $k = 0$ 时，操作二和三都没有意义。这就是一个简单的 bfs 走迷宫问题。
时间复杂度 $O(nm)$，期望得分 $20$ 分。结合算法一可得 $40$ 分。
### 算法三
当 $k$ 比较小且 $h \leq 1$ 时，不需要操作 $3$。
于是可以进行这样的 bfs：
- 在非传送格子上正常进行四联通 bfs。
- 在传送格子上时，除了进行四联通 bfs，还枚举所有的其它的传送阵，尝试传送到其它格子上去。
一共有 $O(nm)$ 个状态，在转移时需要 $O(k)$ 的时间枚举其它的传送阵。总时间复杂度为 $O(nmk)$。期望得分 $15$ 分。结合算法一、二可得 $55$ 分。
### 算法四
注意到操作 3 只会在传送之前一秒进行，可以把这两个操作绑定。
注意到操作 2 和 3 一起做需要两秒。为了不破坏 bfs 时『每步时间增加 1』的性质，可以设 $dis_{x,y,0/1}$ 表示走到 $(x,y)$ 格子，且该格子的高度没有改变/刚刚把该格子的高度改变成其他任意正整数的最短用时。
此时的转移是：
1. 正常的四联通转移。
2. $dis_{x,y,0}$ 转移到 $dis_{x,y,1}$，表示这一秒改了格子的高度。
3. （如果是传送阵）从 $dis_{x,y,0}$ 转移到其他高度相同的传送阵。
4. （如果是传送阵）从 $dis_{x,y,1}$ 转移到其他高度不同的传送阵。
仍然有 $O(nm)$ 个状态，在转移时需要 $O(k)$ 的时间枚举其它的传送阵。总时间复杂度为 $O(nmk)$。期望得分 $70$ 分。
### 算法五（关键算法）
本题的 key conclusion 是：传送至多会使用一次，且一定是离起点最近的传送阵传送到离终点最近的传送阵（无论他们的高度是否一样，当然有高度相同的优先用高度相同的）。
证明：
先证至多传送一次。假设最终方案是 $s ...A - B...C-D...t$，这里 $A,B,C,D$ 是四个传送阵，$s,t$ 是起点终点，$-$ 表示一次传送。考虑 $A-B$ 和 $C-D$ 的过程使用了至少 $2\mathrm s$，而 $A$ 能直接传送到 $D$，花费时间至多是 $2\mathrm s$（先改变 $A$ 的高度，再穿过去）。所以直接从 $A$ 走到 $D$ 的花费不会高于假设里的花费。
再证明一定是离起点最近的传送阵传送到离终点最近的传送阵。如果两个阵的高度相同，此时显然是最优的（假设最优解使用了传送）；如果两个阵高度不同，则传送总过程花费 $2\mathrm s$。如果为了找两个相同高度的阵传送，则至少要再走一步，花费 $1s$，传送再用 $1s$，此时不会比直接走最近的阵优。
由此命题得证。
于是从 $(1,1)$ 开始 bfs 出起点距所有点的距离，找出离起点最近的所有传送阵；然后从终点再做一次 bfs，同样找出离终点最近的传送阵。
检查离起点最近的阵中和里终点最近的阵中有没有等高的。如果有，则答案就是直接走过去和从起点走到传送阵传送并走到终点的时间取最小值；如果没有，把后者的时间加一取最小值。
$h \leq 1$ 时，无需检查是否等高，时间复杂度 $O(nm)$，期望得分 $65$ 分；
$h > 1$ 但 $k$ 比较小时，检查两类传送阵是否有等高的可以 $O(k^2)$ 枚举，时间复杂度 $O(nmk^2)$。
这两种情况期望得分共 $85$ 分。
### 算法六
称离起点或终点距离最近的传送阵为『有效传送阵』。
在造数据的时候发现无法造出 $O(nm)$ 个有效传送阵的数据。有一个符合直觉的猜测时有效传送阵的个数只有 $O(\min(n,m))$ 个，但是我无法给出合理的证明。
事实上数据里有效传送阵确实只有 $O(\min(n,m))$ 个。于是暴力枚举传送阵对检查高度的时间复杂度其实是 $O(n^2)$ 的（认为 $n,m$ 同阶）。设有效传送阵有 $t$ 个，则算法时间复杂度为 $O(nm + t^2)$，可以得到 $100$ 分。
### 算法七
事实上存在 $O(k)$ 的检查高度方法：
先扫一遍离起点最近的传送阵，用一个桶记录这些传送阵的高度（$c_x = 1$ 表示离起点最近的传送阵中有一个高度为 $x$ 的）。
然后扫一遍离终点最近的传送阵。对每个传送阵看它的高度在桶里是否出现。如果出现则表示找到了一对同高度的传送阵。
这样就可以做到 $O(nm + k)$ 了。期望得分 $100$ 分。
## Code
std 实现的是算法 7。
事实上从起点和终点分别进行的两次 bfs 在流程上没有任何区别，只是起终点不同。于是可以写成一个函数，通过传入起点和距离数组参数的形式来完成两次 bfs 调用。
据说有人写 deque 被卡空间了，但是 std 只有 130M 空间（
```cpp
#include <cstring>
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
const int maxn = 3003;
const int INF = 0x3f3f3f3f;
int n, m, k;
int h[maxn][maxn], d1[maxn][maxn], d2[maxn][maxn];
bool isTrans[maxn][maxn];
bool col[maxn * maxn];
std::vector<std::pair<int, int>> trans;
int bfs(int bx, int by, int ex, int ey, int d[][maxn]);
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> n >> m >> k;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
std::cin >> h[i][j];
}
}
for (int i = 1, x, y; i <= k; ++i) {
std::cin >> x >> y;
isTrans[x][y] = true;
trans.push_back(std::make_pair(x, y));
}
memset(d1, 0x3f, sizeof d1);
memset(d2, 0x3f, sizeof d2);
int dis1 = bfs(1, 1, n, m, d1);
int dis2 = bfs(n, m, 1, 1, d2);
int ans = std::min(d1[n][m], dis1 + dis2 + 2);
int cnt1 = 0, cnt2 = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) if (d1[i][j] == dis1 && isTrans[i][j]) {
col[h[i][j]] = true;
++cnt1;
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) if (d2[i][j] == dis2 && isTrans[i][j]) {
if (col[h[i][j]]) ans = std::min(ans, dis1 + dis2 + 1);
++cnt2;
}
}
if (ans == INF) ans = -1;
std::cout << ans << std::endl;
}
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
int bfs(int bx, int by, int ex, int ey, int d[][maxn]) {
int ret = INF;
std::queue<std::pair<int, int>> Q;
d[bx][by] = 0;
for (Q.push(std::make_pair(bx, by)); !Q.empty(); Q.pop()) {
int x = Q.front().first, y = Q.front().second;
if (ret == INF && isTrans[x][y]) ret = d[x][y];
for (int i = 0; i < 4; ++i) {
int px = dx[i] + x, py = dy[i] + y;
if (px && py && px <= n && py <= m && h[px][py] && d[px][py] == INF) {
d[px][py] = d[x][y] + 1;
Q.push(std::make_pair(px, py));
}
}
}
return ret;
}
```
## Generator
前四个点造出来以后手搓改了数据。
```cpp
const int maxn = 8005;
int h[maxn][maxn], dis[maxn][maxn], cnt[maxn * maxn];
const int INF = 0x3f3f3f3f;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
void bfs(int bx, int by, int n, int m, int d[][maxn]) {
std::queue<std::pair<int, int>> Q;
d[bx][by] = 0;
for (Q.push(std::make_pair(bx, by)); !Q.empty(); Q.pop()) {
int x = Q.front().first, y = Q.front().second;
for (int i = 0; i < 4; ++i) {
int px = dx[i] + x, py = dy[i] + y;
if (px && py && px <= n && py <= m && h[px][py] && d[px][py] == INF) {
++cnt[d[px][py] = d[x][y] + 1];
Q.push(std::make_pair(px, py));
}
}
}
}
void makedata(int T) {
int n = 3000, m = 3000, k = 9000000, lim = 4000000;
if (T <= 4) {
n = m = 4;
if (T <= 2) k = 0;
else k = 2;
if (T <= 3) lim = 1;
else lim = 4;
} else if (T <= 10) {
n = m = 50;
if (T <= 6) k = 0;
else k = -1;
if (T <= 8) lim = 1;
else lim = n * m;
} else {
if (T <= 12) k = 0;
else if (T <= 14) k = 10;
else k = -1;
if ((T <= 13) || (T >= 15 && T <= 17)) lim = 1;
}
if (T >= 5) {
m -= modx(5);
n -= modx(6);
if (lim > 1) lim = n * m;
}
if (k == -1) {
k = modx(n * m) + 1;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (lim == 1) {
h[i][j] = (rnd() % 100) ? 1 : 0;
}
else if (lim >= 10) {
if (rnd() % 4) h[i][j] = modx(10);
else h[i][j] = modx(lim + 1);
} else {
h[i][j] = modx(lim + 1);
}
}
}
for (int i = n / 3 * 2; i <= n; ++i) h[i][m / 3 * 2] = 0;
for (int i = 1; i <= m / 3 * 2; ++i) h[n / 3 * 2][i] = 0;
if ((T & 1) == 0) {
if (lim > 1) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) if (h[i][j]) {
h[i][j] = (i - 1) * n + j;
}
}
}
}
memset(dis, 0x3f, sizeof(dis));
memset(cnt, 0, sizeof(cnt));
bfs(1, 1, n, m, dis);
int d = std::max_element(cnt + 1, cnt + 1 + n * m) - cnt;
std::vector<std::pair<int, int>> p;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) if (dis[i][j] == d) p.push_back(std::make_pair(i,j));
}
memset(dis, 0x3f, sizeof(dis));
memset(cnt, 0, sizeof cnt);
bfs(n, m, n, m, dis);
d = std::max_element(cnt + 1, cnt + 1 + n * m) - cnt;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) if (dis[i][j] == d) p.push_back(std::make_pair(i,j));
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) if (dis[i][j] == 0x3f3f3f3f && h[i][j]) p.push_back(std::make_pair(i,j));
}
std::sort(p.begin(), p.end());
auto ed = std::unique(p.begin(), p.end());
k = std::min(k, int(ed - p.begin()));
printf("%d %d %d\n", n, m, k);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
printf("%d%c", h[i][j], " \n"[j == m]);
for (int i = 0; i < k; ++i) printf("%d %d\n", p[i].first, p[i].second);
}
```