题解 P5195 【[USACO05DEC]Knights of Ni 骑士】

杨铠远 · 2019-08-28 19:53:05 · 题解

好像都是两遍bfs或者dfs

其实跑一遍分层图就可以了

在骑士处连接分层图，具体看代码

//Code by : Y-k-y
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <set>
#define ll long long
const int N=10000010;
using namespace std;
inline int rnd(){
    int res=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){res=res*10+ch-'0';ch=getchar();}
    return res*f;
}
inline void wr(int x){
    if(x<0){putchar('-');x=-x;}if(x>9) wr(x/10);putchar(x%10+'0');
}
int n,m,sx,sy,tot;
int a[1005][1005];
struct pp{
    int v,nxt;
}edge[N];
int head[N],d[N],id[1004][1005];
bool ans[N];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
bool vis[N];
inline void add(int u,int v){
    edge[++tot].nxt=head[u],head[u]=tot;
    edge[tot].v=v;
}
inline int chk(int x,int y){
    return x>0&&x<=n&&y>0&&y<=m&&a[x][y]!=1;
}
inline int num(int x,int y){
    return (x-1)*m+y;
}
inline void spfa(){
    queue<int>q;
    q.push(id[sx][sy]);vis[id[sx][sy]]=1;
    memset(d,0x3f,sizeof(d));
    d[id[sx][sy]]=0;
    while(!q.empty()){
        int u=q.front();q.pop();vis[u]=0;
        for(int i=head[u];i;i=edge[i].nxt){
            int v=edge[i].v;
            if(d[v]>d[u]+1){
                d[v]=d[u]+1;
                if(!vis[v]){
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
}
int main(){
    cin>>m>>n;//n m的顺序。。。 
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
        a[i][j]=rnd(),id[i][j]=num(i,j);//类似hash吧 
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]==1)continue;
            for(int k=0;k<4;k++){
                int x=i+dx[k],y=j+dy[k];
                if(chk(x,y)){
                    add(id[i][j],id[x][y]);
                    add(id[i][j]+n*m,id[x][y]+n*m);//两个图上都要连边 
                }
            }
            if(a[i][j]==4){
                add(id[i][j],id[i][j]+n*m);//骑士，连接两个图 
            }
            if(a[i][j]==3){
                ans[id[i][j]]=1;
            }
            if(a[i][j]==2){
                sx=i,sy=j;
            }
        }
    }
    spfa();
    int sum=1<<30;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(ans[id[i][j]]){
                sum=min(sum,d[id[i][j]+n*m]);
            }
        }
    }
    wr(sum-1);//因为在跳图的时候，也算了一个距离，所以减一 
    return 0;
}