题解：P14402 [JOISC 2016] 危险的滑冰 / Dangerous Skating

jcs_pp · 2026-10-22 15:30:36 · 题解

简单证明一下，可以发现新增的冰块不会对答案产生影响。

• 冰块不会产生不利影响，若路径会经过一个点两次，这条路一定不是最优的。
• 冰块不会产生有利影响，稍微模拟一下就可以发现，要再次回到冰块旁边要绕一个大圈，肯定不是最优。

所以地形可以直接当它不改变，这题就转化为了一个普普通通的迷宫问题。

有两种移动方式，一种直接窜到一个冰块前面，花费一次移动；一种产生一个冰块，并移动到远端位置，再回来，这样可以用两次移动到达当前位置的旁边一个位置。

因为两种移动花费不同，所以用 Dijkstra 算法跑最短路，时间复杂度 O(RC \log{RC})。

Code:

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

#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define repb(i, a, b) for(int i = (a); i >= (b); --i)

const int N = 2005;
int n, m;
char a[N][N];
int sx, sy, ex, ey;

struct Node{
    int x, y, step;
    bool operator < (const Node & b) const{
        return step > b.step;
    }
};
priority_queue<Node> q;
int vis[N][N];
int dis[N][N];
int rx[N][N], ry[N][N], lx[N][N], ly[N][N];
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

void get_new(int px, int py, int nx, int ny, int w){
    if(dis[nx][ny] > dis[px][py] + w){
        dis[nx][ny] = dis[px][py] + w;
        q.push(Node{nx, ny, dis[nx][ny]});
    }
}

void DJ(){
    memset(dis, 0x3f, sizeof dis);
    q.push(Node{sx, sy, 0});
    dis[sx][sy] = 0;
    while(!q.empty()){
        auto p = q.top(); q.pop();
        if(vis[p.x][p.y]) continue;
        vis[p.x][p.y] = 1;
        if(p.x == ex && p.y == ey){
            cout << p.step << '\n';
            return;
        }
        rep(i, 0, 3){
            int nx = p.x + dx[i], ny = p.y + dy[i];
            if(a[nx][ny] != '#') get_new(p.x, p.y, nx, ny, 2);
        }
        get_new(p.x, p.y, p.x, ly[p.x][p.y], 1);
        get_new(p.x, p.y, p.x, ry[p.x][p.y], 1);
        get_new(p.x, p.y, lx[p.x][p.y], p.y, 1);
        get_new(p.x, p.y, rx[p.x][p.y], p.y, 1);
    }
    cout << -1;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m;
    rep(i, 1, n){
        rep(j, 1, m){
            cin >> a[i][j];
        }
    }
    rep(i, 1, n){
        rep(j, 1, m){
            if(a[i][j] == '#') ly[i][j] = 1e9;
            else ly[i][j] = min(j, ly[i][j - 1]);
        }
        repb(j, m, 1){
            if(a[i][j] == '#') ry[i][j] = -1e9;
            else ry[i][j] = max(j, ry[i][j + 1]);
        }
    }
    rep(j, 1, m){
        rep(i, 1, n){
            if(a[i][j] == '#') lx[i][j] = 1e9;
            else lx[i][j] = min(i, lx[i - 1][j]);
        }
        repb(i, n, 1){
            if(a[i][j] == '#') rx[i][j] = -1e9;
            else rx[i][j] = max(i, rx[i + 1][j]);
        }
    }

    cin >> sx >> sy >> ex >> ey;

    DJ();

    return 0;
}