U254385 秘密通道（10.16&portal）题解

· · 个人记录

前言

地图转最短路模型。

题意

有一张 n × m 的地图，里面包含主角的起、终点，墙（不能通过），空地。

主角可以向上下左右移动一步（花费 1 单位时间），可以通过对墙的两次射击打开一个秘密通道（进去一个可以瞬移到另一个通道对应墙前的空地）（花费 0 单位时间）。

求主角从终点到终点的最短时间。

基本思路

由于 4\le n,m \le 500。用普通的模拟+爆搜肯定是 T 飞了的，对于一张地图的处理（这里所说的地图是一个数字或字符构成的矩阵）无非就两种（至少我只知道 2 种）：

本题应考虑方案 2 。

详细思路

开通道的目的是什么？肯定是为了快速传送啊。如果开通道更加慢了，还不如不开。。。

要想比较二者之间的优劣，必定要将其量化。令到达传送目的地的时间为 t，到达传送点的时间为 t_2。显而易见的——t = t_2。考虑预处理出每个空地到其最近的传送点的距离 f_{i,j}，这就是它到所有传送目的地的距离。

既然有了量化指标，能够比较出路径之间的优劣。我们发现最短路正好需要这些特性，考虑对地图建图。

加边的过程可以在 Dijkstra 的过程中进行，也是无所谓有向无向的。

完整代码

#include <bits/stdc++.h>

using namespace std;

const int N = 505, inf = 25000;

struct L{
  int x, y, l;
  bool operator<(const L &_l) const { return l > _l.l; }
};

struct E{
  vector<L> e;
  int d = inf;
} e[N * N];

int n, m, t, bx, by, ex, ey, ans = inf;
int dir[5][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
int vis[N][N], f[N][N];
char mp[N][N];

priority_queue<L> que;

int p(int x, int y) {
  return (x - 1) * m + y;
}

void Dijkstra() {
  for (que.push({bx, by, 0}); !que.empty(); ) {
    L h = que.top();
    que.pop();
    if (h.l < e[p(h.x, h.y)].d) {
      e[p(h.x, h.y)].d = h.l;
      for (int i = 0; i < 4; i++) {
        int rx = h.x, ry = h.y, nx = rx + dir[i][0], ny = ry + dir[i][1];
        if (mp[nx][ny] != '#' && nx >= 1 && ny >= 1 && nx <= n && ny <= m) {
          que.push({nx, ny, h.l + 1});
          for ( ; mp[rx + dir[i][0]][ry + dir[i][1]] != '#'; rx += dir[i][0], ry += dir[i][1]) {
          }
          que.push({rx, ry, h.l + f[h.x][h.y]});
        }
      }
    }
  }
}

void S(int sx, int sy, int x, int y, int step) {
  if (step >= f[sx][sy] || vis[x][y] || x < 1 || y < 1 || x > n || y > m) {
    return;
  }
  if (mp[x][y] == '#') {
    f[sx][sy] = step;
    return;
  }
  vis[x][y] = 1;
  for (int i = 0; i < 4; i++) {
    S(sx, sy, x + dir[i][0], y + dir[i][1], step + 1);
  }
  vis[x][y] = 0;
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      cin >> mp[i][j];
      f[i][j] = e[p(i, j)].d = inf;
      if (mp[i][j] == 'C') {
        bx = i, by = j;
      } else if (mp[i][j] == 'F') {
        ex = i, ey = j;
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (mp[i][j] != '#') {
        S(i, j, i, j, 0);
      }
    }
  }
  Dijkstra();
  if (e[p(ex, ey)].d == inf) {
    cout << "nemoguce";
  } else {
    cout << e[p(ex, ey)].d;
  }
  return 0;
}

总结