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

· · 题解

模拟赛题，赛时由于糖了写了个 O(n^3) 的。

首先，显然可以通过耗费 1 的代价走到上下左右连续最远的非冰块的格子，通过耗费 2 的代价走到相邻的格子。

然后，直接跑最短路就可以过了？

浅证一下：如果你想到达一个格子，那么这个格子相邻肯定有冰块，所以你就只能来回挪；如果这是一个新的有冰块的格子，那么你要再次利用它需要至少 3 次，所以肯定会有决策不比再次利用它劣。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
constexpr int N=1e3+5;
char s[N][N];
int dis[N][N],sx,sy,tx,ty;
int vis[N][N],L[N][N],R[N][N],U[N][N],D[N][N];
struct node{
    int i,j;
};
vector<node>e[N*N];
inline void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;++i)cin>>s[i];
    cin>>sx>>sy>>tx>>ty;
    memset(dis,0x3f,sizeof(dis));
    e[0].emplace_back((node){sx,sy});
    for(int i=1;i<=n;++i){
        for(int j=m;j>=1;--j)s[i][j]=s[i][j-1];
        for(int j=1,now=1;j<=m;++j){
            if(s[i][j]=='#')now=j+1;
            else L[i][j]=now;
        }
        for(int j=m,now=m;j>=1;--j){
            if(s[i][j]=='#')now=j-1;
            else R[i][j]=now;
        }
    }
    for(int i=1;i<=m;++i){
        for(int j=1,now=1;j<=n;++j){
            if(s[j][i]=='#')now=j+1;
            else U[j][i]=now;
        }
        for(int j=n,now=n;j>=1;--j){
            if(s[j][i]=='#')now=j-1;
            else D[j][i]=now;
        }
    }
    int di=0;
    while(1){
        while(di<=n*m&&e[di].empty())++di;if(di>n*m)break;
        node u=e[di].back();e[di].pop_back();
        if(vis[u.i][u.j])continue;
        if(u.i==tx&&u.j==ty){cout<<di;return;}
        vis[u.i][u.j]=1;
        if(s[u.i][u.j-1]=='.'){
            if(dis[u.i][L[u.i][u.j]]>di+1)dis[u.i][L[u.i][u.j]]=di+1,e[di+1].emplace_back((node){u.i,L[u.i][u.j]});
            if(dis[u.i][u.j-1]>di+2)dis[u.i][u.j-1]=di+2,e[di+2].emplace_back((node){u.i,u.j-1});
        }
        if(s[u.i][u.j+1]=='.'){
            if(dis[u.i][R[u.i][u.j]]>di+1)dis[u.i][R[u.i][u.j]]=di+1,e[di+1].emplace_back((node){u.i,R[u.i][u.j]});
            if(dis[u.i][u.j+1]>di+2)dis[u.i][u.j+1]=di+2,e[di+2].emplace_back((node){u.i,u.j+1});
        }
        if(s[u.i-1][u.j]=='.'){
            if(dis[U[u.i][u.j]][u.j]>di+1)dis[U[u.i][u.j]][u.j]=di+1,e[di+1].emplace_back((node){U[u.i][u.j],u.j});
            if(dis[u.i-1][u.j]>di+2)dis[u.i-1][u.j]=di+2,e[di+2].emplace_back((node){u.i-1,u.j});
        }
        if(s[u.i+1][u.j]=='.'){
            if(dis[D[u.i][u.j]][u.j]>di+1)dis[D[u.i][u.j]][u.j]=di+1,e[di+1].emplace_back((node){D[u.i][u.j],u.j});
            if(dis[u.i+1][u.j]>di+2)dis[u.i+1][u.j]=di+2,e[di+2].emplace_back((node){u.i+1,u.j});
        }
    }
    cout<<-1;
}
int main()
{

    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    solve();
    return 0;
}