题解：AT_s8pc_5_e Broken Skateboard

· · 题解

思路

我们考虑对于每个石块连边，将其四个正方向的石块进行连边，同时也需要与 G 当作石块。

因为从一个方块到 G 不等价于 G 到这个方块，所以我们只能枚举 G 到某个方块的经过石块的个数。

我只需要统计每个石块到 G 的最小步数，同时易证得，最小步数为 \min(C+1, n+m)。

那么冰块呢？

冰块只是在石块的基础上加的，如果同行同列的石块都达不到 G，这个冰块也肯定达不到 G。

所以计算完石块到 G 的最小时间后，枚举石块，再其枚举同行同列的冰块统计答案即可。

但是此时的时间复杂度为 O((H+W)C\log(C))。

瓶颈在于 dijkstra 中的优先队列。

我们发现朴素版 dijkstra 时间复杂度更优，只有 \min(C+1, H+W) 步数，C 个点，常数为 4。

所以只用使用朴素版 dijkstra 即可。

这里需要注意的是，这里是多层最短路，不能每次找最小值进行比较，而是所有的点进行松弛。

然后就做完了。

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3+10;
const int C = 8e3+10;

struct node {
    int v, w;
};

int n, m;
int a[N][N];

int dfn[N][N], cur;
pair<int, int> id[C];

int st;
int s, e;

int cnt;
vector<node> g[C];

int d[C][2*N];

int output[N][N];

__inline void bfs() {
    for (int i = 1;i<= min(cnt+1, n+m)+1;i++) {
        d[st][i] = 0;
    }
    for (int i = min(cnt+1, n+m)+1;i>= 2;i--) {
        for (int j = 1;j<= cnt;j++) {
            if (d[j][i] == 0x3f3f3f3f) continue;

            for (auto kv : g[j]) {
                d[kv.v][i-1] = min(d[kv.v][i-1], kv.w*i + d[j][i]);
            }
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m; char ch;
    for (int i = 1;i<= n;i++) {
        for (int j = 1;j<= m;j++) {
            cin >> ch;
            if (ch == '.') a[i][j] = 1;
            else if (ch == '#') a[i][j] = 2, cnt++;
            else a[i][j] = 2, s = i, e = j, cnt++;
            if (a[i][j] != 2) continue;
            dfn[i][j] = ++cur, id[cur] = {i, j};
            if (i == s && j == e) st = cur;
        }
    } // 下面在进行连边
    int last = 0, k = 0;
    for (int i = 1;i<= n;i++) {
        last = 0, k = 0;
        for (int j = 1;j<= m;j++) {
            if (a[i][j] != 2) continue;
            if (last != 0) g[dfn[i][j]].push_back({last, j-k});
            last = dfn[i][j], k = j;
        }
        last = 0, k = 0;
        for (int j = m;j>= 1;j--) {
            if (a[i][j] != 2) continue;
            if (last != 0) g[dfn[i][j]].push_back({last, k-j});
            last = dfn[i][j], k = j;
        }
    }
    for (int j = 1;j<= m;j++) {
        last = 0, k = 0;
        for (int i = 1;i<= n;i++) {
            if (a[i][j] != 2) continue;
            if (last != 0) g[dfn[i][j]].push_back({last, i-k});
            last = dfn[i][j], k = i;
        } last = 0, k = 0;
        for (int i = n;i>= 1;i--) {
            if (a[i][j] != 2) continue;
            if (last != 0) g[dfn[i][j]].push_back({last, k-i});
            last = dfn[i][j], k = i;
        }
    }
    memset(output, 0x3f, sizeof output);
    memset(d, 0x3f, sizeof d);
    bfs();
    for (int i = 1;i<= cur;i++) { // 统计所有点的答案
        int x = id[i].first, y = id[i].second;
        int ny = y; output[x][y] = min(output[x][y], d[dfn[x][y]][1]); ny--;
        int dis = d[dfn[x][y]][1];
        while ((ny + 1 == y || a[x][ny+1] != 2) && ny > 0) {
            output[x][ny] = min(output[x][ny], dis + y - ny);
            ny--;
        } ny = y; ny++;
        while ((ny - 1 == y || a[x][ny-1] != 2) && ny <= m) {
            output[x][ny] = min(output[x][ny], dis + ny - y);
            ny++;
        } int nx = x; nx--;
        while ((nx+1 == x || a[nx+1][y] != 2) && nx > 0) {
            output[nx][y] = min(output[nx][y], dis + x - nx);
            nx--;
        } nx = x; nx++;
        while ((nx-1 == x || a[nx-1][y] != 2) && nx <= n) {
            output[nx][y] = min(output[nx][y], dis + nx - x);
            nx++;
        }
    }
    for (int i = 1;i<= n;i++) {
        for (int j = 1;j<= m;j++) {
            if (output[i][j] == 0x3f3f3f3f) printf("%d ", -1);
            else printf("%d ", output[i][j]);
        } printf("\n");
    }
    return 0;
}