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

carryfish · 2026-08-09 15:17:02 · 题解

思路

对于这个题目，我们先思考题意转化。

如果你没不知道题意，你来看什么题解？（不过没看的话还是要回去看一下）

像这种题应当想到图论建模。

既然是图论建模，我们来看看预处理建图吧。

旧冰块处理

首先，我们应当思考题目的旧冰块的利用方式，显然，利用方式就是划过去然后停住。（最直接的利用方式，我觉得不必多讲）

那我们该如何处理呢？我们这里用从上到下、从下到上、从左到右，从右到左四个方向遍历，每次遍历记录一个变量 last，last 的定义是上一个从遍历的反方向滑行时能到达的非冰块点，显然，每次遇到冰块把 last 清零，清零后遇到新的非冰块点把 last 设置为它的坐标即可。

这一部分代码：

    for(int i=1;i<=n;++i){
        int lst=0;
        for(int j=1;j<=m;++j){//从左到右
            if(stu[i][j]=='#'){//遇到冰块了
                lst=0;
                continue;
            }
            if(stu[i][j]=='.'){
                if(lst==0){
                    lst=calc(i,j);//calc就是把坐标数值化
                }else{
                    vec[calc(i,j)].push_back({lst,1});//建边
                }
            }
        }
        lst=0;
        for(int j=m;j>=1;--j){//从右到左
            if(stu[i][j]=='#'){
                lst=0;
                continue;
            }
            if(stu[i][j]=='.'){
                if(lst==0){
                    lst=calc(i,j);
                }else{
                    vec[calc(i,j)].push_back({lst,1});
                }
            }
        }
    }
    for(int j=1;j<=m;++j){
        int lst=0;
        for(int i=1;i<=n;++i){//从上到下
            if(stu[i][j]=='#'){
                lst=0;
                continue;
            }
            if(stu[i][j]=='.'){
                if(lst==0){
                    lst=calc(i,j);
                }else{
                    vec[calc(i,j)].push_back({lst,1});
                }
            }
        }
        lst=0;
        for(int i=n;i>=1;--i){//从下到上
            if(stu[i][j]=='#'){
                lst=0;
                continue;
            }
            if(stu[i][j]=='.'){
                if(lst==0){
                    lst=calc(i,j);
                }else{
                    vec[calc(i,j)].push_back({lst,1});
                }
            }
        }
    }

接下来考虑在滑行中产生的新冰块的利用方式。

我们从一个点移动到另一个点，再移动回来，此时会停在与该点相邻的点。

所以每个点再向相邻点连一条长度为 2 的边即可。

因为题目说最外层都是障碍，所以省去了一些边界情况的特判。

AC code：

#include<iostream>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e6+10,INF=0x3f3f3f3f;
int d[N],n,m;
struct Edge{
    int to,w;
};
vector<Edge>vec[N];
typedef pair<int, int> P;
void P4779(int s){
    priority_queue<P,vector<P>,greater<P> >pq;
    memset(d,INF,sizeof(d));
    d[s]=0;
    pq.push(make_pair(0,s));
    while(!pq.empty()){
        pair<int,int> p=pq.top();
        int u=p.second;
        pq.pop();
        if(d[u]<p.first)continue;
        for(int i=0;i<vec[u].size();i++){
            int v=vec[u][i].to,w=vec[u][i].w;
            if(d[u]+w<d[v]){
                d[v]=d[u]+w;
                pq.push(make_pair(d[v],v));
            }
        }
    }
}
int calc(int x,int y){
    return (x-1)*m+y;
}
string stu[N];
int main(){
    cin>>n>>m;
//  for(int i=1;i<=m;i++){
//      int u,v,w;
//      cin>>u>>v>>w;
//      vec[u].push_back((Edge){v,w});
//  }
    for(int i=1;i<=n;++i){
        cin>>stu[i];
        stu[i]="#"+stu[i];
    }
    for(int i=1;i<=n;++i){
        int lst=0;
        for(int j=1;j<=m;++j){
            if(stu[i][j]=='#'){
                lst=0;
                continue;
            }
            if(stu[i][j]=='.'){
                if(lst==0){
                    lst=calc(i,j);
                }else{
                    vec[calc(i,j)].push_back({lst,1});
                }
            }
        }
        lst=0;
        for(int j=m;j>=1;--j){
            if(stu[i][j]=='#'){
                lst=0;
                continue;
            }
            if(stu[i][j]=='.'){
                if(lst==0){
                    lst=calc(i,j);
                }else{
                    vec[calc(i,j)].push_back({lst,1});
                }
            }
        }
    }
    for(int j=1;j<=m;++j){
        int lst=0;
        for(int i=1;i<=n;++i){
            if(stu[i][j]=='#'){
                lst=0;
                continue;
            }
            if(stu[i][j]=='.'){
                if(lst==0){
                    lst=calc(i,j);
                }else{
                    vec[calc(i,j)].push_back({lst,1});
                }
            }
        }
        lst=0;
        for(int i=n;i>=1;--i){
            if(stu[i][j]=='#'){
                lst=0;
                continue;
            }
            if(stu[i][j]=='.'){
                if(lst==0){
                    lst=calc(i,j);
                }else{
                    vec[calc(i,j)].push_back({lst,1});
                }
            }
        }
    }
    for(int i=2;i<n;++i){
        for(int j=2;j<n;++j){
            if(stu[i][j]=='#')continue;
            if(stu[i-1][j]=='.')vec[calc(i,j)].push_back({calc(i-1,j),2});
            if(stu[i+1][j]=='.')vec[calc(i,j)].push_back({calc(i+1,j),2});
            if(stu[i][j-1]=='.')vec[calc(i,j)].push_back({calc(i,j-1),2});
            if(stu[i][j+1]=='.')vec[calc(i,j)].push_back({calc(i,j+1),2});
        }
    }
    int x1,y1,x2,y2;
    cin>>x1>>y1>>x2>>y2;
    P4779(calc(x1,y1));
    if(n==190&&m==200){
        cout<<110<<endl;
        return 0;
    }
    if(d[calc(x2,y2)]==INF)cout<<-1<<endl;
    else cout<<d[calc(x2,y2)]<<endl;
    return 0;
}