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

· · 题解

CSP-S 模拟赛的一题，来写题解。

首先我们初步观察题目发现，题目给出的图是动态变化的，并且当前操作可能会对后续操作产生影响，所以我们先争取把这个过程转成静态。

对于一步向右移动，设初始位置为 (i,j)，移动到了 (i,j+k)，且 (i,j+k+1) 为障碍物。

那么当我们再从 (i,j+k) 移走时，(i,j) 就会变为冰块，现在我们考虑该冰块对后续求解产生影响的形式。

很明显影响了 (i,j+1)、(i,j-1)、(i-1,j)、(i+1,j)，因为如果这个冰块要产生影响，必须有一步因这个冰块的存在而停止。

但是我们已经走过了 (i,j)，所以当我们要移动到相邻格子时，我们可以像那个方向滑，再从相反的方向滑回来，由于 (i,j) 已经产生了冰块，所以就恰好会停在目标的相邻位置。该方案的移动代价为 2 步。

可以证明，不存在别的方法，可以在 1 步以内的代价走到相邻格子，未来也不会。

因此我们证明了所有步骤产生的冰块都不会对后续操作产生影响。

但是因为我们构造了上面的方案，所以当前格子 (i,j) 对未来两步有可能产生影响。

发现我们构造出的方案可以看作一个整体，即移动到相邻格子，代价为 2 步。

现在我们已经得到了所有的移动方案，即移动到相邻的一格，代价为 2 步，和移动到所有方向最近的冰块的前一个位置，代价为 1 步。

所以我们对于我们建出来的图跑最短路即可。（注意不能用 BFS，因为边权不都为 1）

时间复杂度 O(N^2\log N)，可过。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pr;
const int N = 2010;
const int INF = 1e9;
int n,m,stx,sty,edx,edy,la[N],vis[N][N],dis[N][N];
int dx[] = {0,-1,0,1},dy[] = {1,0,-1,0};
char a[N][N];
pr to[N][N][4];
struct str{
    int ds,x,y;
    bool operator < (const str & _) const {
        return ds > _.ds;
    }
};
inline void init(){
    for(int i = 1;i <= n;++i){
        int nw = 0;
        for(int j = 1;j <= m;++j){
            dis[i][j] = INF;
            if(a[i][j] == '.'){
                if(i - la[j] > 1) to[i][j][0] = make_pair(la[j] + 1,j);
                if(j - nw > 1) to[i][j][1] = make_pair(i,nw + 1);
            }
            else{
                nw = j;
                la[j] = i;
            }
        }
    }
    for(int i = n;i >= 1;--i){
        int nw = 0;
        for(int j = m;j >= 1;--j){
            if(a[i][j] == '.'){
                if(la[j] - i > 1) to[i][j][2] = make_pair(la[j] - 1,j);
                if(nw - j > 1) to[i][j][3] = make_pair(i,nw - 1);
            }
            else{
                nw = j;
                la[j] = i;
            }
        }
    }
}
inline void bfs(){
    priority_queue<str> q;
    q.push((str){0,stx,sty});
    dis[stx][sty] = 0;
    while(!q.empty()){
        str p = q.top();
        q.pop();
        int x = p.x,y = p.y;
        if(vis[x][y]) continue;
        vis[x][y] = 1;
        int ds = dis[x][y];
        for(int i = 0;i < 4;++i){
            int nx = dx[i] + x;
            int ny = dy[i] + y;
            if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && a[nx][ny] != '#' && dis[nx][ny] > dis[x][y] + 2){
                int ndis = ds + 2;
                dis[nx][ny] = ndis;
                if(!vis[nx][ny]) q.push((str){ndis,nx,ny});
            }
        }
        for(int i = 0;i < 4;++i){
            auto [nx,ny] = to[x][y][i];
            if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && a[nx][ny] != '#' && dis[nx][ny] > dis[x][y] + 1){
                int ndis = ds + 1;
                dis[nx][ny] = ndis;
                if(!vis[nx][ny]) q.push((str){ndis,nx,ny});
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i <= n;++i){
        for(int j = 1;j <= m;++j){
            cin >> a[i][j];
        }
    }
    init();
    cin >> stx >> sty >> edx >> edy;
    bfs();
    if(!vis[edx][edy]) cout << -1;
    else cout << dis[edx][edy];
    return 0;
}