题解：AT_joisc2016_j 危険なスケート

· · 题解

模拟赛做到的，写发题解总结一下。

考虑从点 (i,j) 出发能走到哪些点，首先可以沿着上下左右任意方向前进直到遇到冰块位置，例如向左走碰到的第一个冰块坐标是 (i, a) ，那么从 (i,j) 出发能走到 (i, a + 1)，其余方向同理。

每次移动会在原位产生一个冰块，例如：

#######
#S....#
#.....#
#.....#
#######

其中 S 为起点，向右走一步为：

#######
##...S#
#.....#
#.....#
#######

再次向左走：

#######
##S..##
#.....#
#.....#
#######

我们发现移动到了初始位置的相邻位置，所以如果四周相邻位置不是冰块的话，我们可以用 2 次操作到达相邻点。这里题目保证四周全是冰块，所以 2 步一定可以到达。

发现每次冰块的位置都会变，不好跑搜索。考虑建图。

从 (i,j) 出发向四个方向上第一个遇到的冰块前一个位置连边，边权为 1，向四周不为冰块的点连边，边权为 2，在这张图上跑最短路即可。本题点数为 10^6 级别，边数大概为 8\times 10^6，跑 dijkstra 可以通过本题。

const int MOD = 1e9 + 7;
const int N = 1e3 + 10;
const int M = 1e6 + 10;
/*====================*/
int n, m;
char mp[N][N];
int r1, r2, c1, c2;
vector<vector<PII>> g;
int xx[] = { 1, -1, 0, 0 };
int yy[] = { 0, 0, 1, -1 };
int idx[N][N];
int cnt;
int l[N][N];
int r[N][N];
int u[N][N];
int d[N][N];
bool vis[M];
/*====================*/
int dis[M];
void dijkstra(int st) {
    priority_queue<PII, vector<PII>, greater<PII>> q;
    q.push({ 0, st });
    for (int i = 1; i <= cnt; ++i) {
        dis[i] = LLONG_MAX;
        vis[i] = 0;
    }
    dis[st] = 0;
    while (!q.empty()) {
        auto [du, u] = q.top(); q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        if (du != dis[u]) continue;
        for (auto [v, w] : g[u]) {
            // cout << u << " " << v << " " << dis[u] << " " << w << " " << dis[v] << endl;
            if (dis[u] + w < dis[v]) {
                dis[v] = dis[u] + w;
                q.push({ dis[v], v });
            }
        }
    }
    return;
}
/*====================*/
void Solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> mp[i][j];
            idx[i][j] = ++cnt;
        }
    }
    for (int i = 1; i <= n; i++) {
        int lst = 1;
        for (int j = 1; j <= m; j++) {
            if (mp[i][j] == '#') lst = j;
            l[i][j] = lst;
        }
        lst = m;
        for (int j = m; j >= 1; j--) {
            if (mp[i][j] == '#') lst = j;
            r[i][j] = lst;
        }
    }
    for (int j = 1; j <= m; j++) {
        int lst = 1;
        for (int i = 1; i <= n; ++i) {
            if (mp[i][j] == '#') lst = i;
            u[i][j] = lst;
        }
        lst = n;
        for (int i = n; i >= 1; i--) {
            if (mp[i][j] == '#') lst = i;
            d[i][j] = lst;
        }
    }
    cin >> r1 >> c1 >> r2 >> c2;
    g.assign(cnt + 5, {});
    for (int i = 2; i < n; i++) {
        for (int j = 2; j < m; j++) {
            if (mp[i][j] == '#') continue;
            for (int z = 0; z < 4; z++) {
                int dx = i + xx[z];
                int dy = j + yy[z];
                if (dx <= 1 || dx >= n || dy <= 1 || dy >= m || mp[dx][dy] == '#') continue;
                g[idx[i][j]].push_back({ idx[dx][dy], 2 });
            }
            g[idx[i][j]].push_back({ idx[i][l[i][j] + 1], 1 });
            g[idx[i][j]].push_back({ idx[i][r[i][j] - 1], 1 });
            g[idx[i][j]].push_back({ idx[u[i][j] + 1][j], 1 });
            g[idx[i][j]].push_back({ idx[d[i][j] - 1][j], 1 });
        }
    }
    dijkstra(idx[r1][c1]);
    cout << (dis[idx[r2][c2]] >= LLONG_MAX / 2 ? -1 : dis[idx[r2][c2]]) << endl;
    return;
}