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

· · 题解

找图论建模题找到这个，然后妙妙了。

思路

首先在矩阵上跑这跑那的，总得建边吧，普通的 bfs 大概不太可以因为那个起点被冻住了然后没有很好的办法标记。

然后问最少几次，都建边完了那就想想最短路。

感觉这个思想有点套路，首先是一个点到下一个冰块需要一步，然后考虑相邻的，一来一回需要两步。那么可能就会有一个问题，这个还是没有考虑后来的冰块啊，那一定都走到那个位置了就是最短了还管什么？然后其他情况可以直接组合

然后就跑最短路就没了。

代码

#include<bits/stdc++.h>
using namespace std;
#define N 1000005
inline int read(){
    int a=0,f=1;
    char c=getchar();
    while(c>'9'||c<'0'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        a=a*10+c-'0';
        c=getchar();
    }
    return a*f;
}
int n,m,s,t;
char c[1005][1005];
int get(int x,int y){//2维转1维
    return (x-1)*m+y;
}
struct node{
    int next,to,w;
}edge[N*8];
int head[N],cnt=0;
void addedge(int u,int v,int w){
    edge[++cnt].next=head[u];
    head[u]=cnt;
    edge[cnt].to=v,edge[cnt].w=w;
}
int bx[4]={0,0,1,-1},by[4]={1,-1,0,0};
void jb(){
    for(int i=2;i<n;i++){//到冰块
        int x=get(i,m-1);
        for(int j=m-1;j>=2;j--){
            if(c[i][j]=='#'){
                x=get(i,j-1);continue;
            }
            addedge(get(i,j),x,1);
        }
        x=get(i,2);
        for(int j=2;j<=m-1;j++){
            if(c[i][j]=='#'){
                x=get(i,j+1);continue;
            }
            addedge(get(i,j),x,1);
        }
    }
    for(int j=2;j<=m-1;j++){
        int x=get(2,j);
        for(int i=2;i<n;i++){
            if(c[i][j]=='#'){
                x=get(i+1,j);continue;
            }
            addedge(get(i,j),x,1);
        }
        x=get(n-1,j);
        for(int i=n-1;i>=2;i--){
            if(c[i][j]=='#'){
                x=get(i-1,j);continue;
            }
            addedge(get(i,j),x,1);
        }
    }
    for(int i=2;i<n;i++)//相邻
        for(int j=2;j<m;j++){
            if(c[i][j]=='#')continue;
            for(int k=0;k<=3;k++){
                int x=bx[k]+i,y=by[k]+j;
                if(c[x][y]=='#')continue;
                addedge(get(i,j),get(x,y),2);
            }
        }
}
struct pnode{
    int u,dis;
    bool operator >(const pnode &a)const{
        return dis>a.dis;
    }
};
priority_queue<pnode,vector<pnode>,greater<pnode> >q;
int dis[N];
bool vis[N];
void dj(int s){
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0,q.push({s,0});
    while(!q.empty()){
        if(vis[t])return;
        pnode now=q.top();
        q.pop();
        int u=now.u;
        if(vis[u])continue;
        vis[u]=1;
        for(int i=head[u];i;i=edge[i].next){
            int v=edge[i].to;
            if(dis[v]>now.dis+edge[i].w){
                dis[v]=now.dis+edge[i].w;
                q.push({v,dis[v]});
            }
        }
    }
}
int main(){
    // freopen("1.in","r",stdin);
    // freopen("1.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>c[i][j];
    int x=read(),y=read(),xx=read(),yy=read();
    s=get(x,y),t=get(xx,yy);
    jb(),dj(s);
    if(dis[t]==0x3f3f3f3f)
        printf("-1\n");
    else
        printf("%d\n",dis[t]);
    return 0;
}