虫洞操纵者

本质上就是bfs，但只不过我们这道题建图有点麻烦，我们得考虑每行的最近点对和每列的，我们要搞虫洞，我们可以用二维数组来装一下在 $(x,y)$ 坐标下，每行或每列的最近 $1$ 的位置，然后每行每列找到之后，我们就将它们建图，最后我们只需要跑个最短路即可解决。

这边注意一下的就是，我们是扩展了图，就是把给定的图的外部全部设为 1。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>

#define x first
#define y second

using namespace std;

typedef pair<int,int>PII;

const int N = 3e6+10,M = 4*N,S=1e3+10;

int e[M],ne[M],h[N],idx;
bool st[N];
int n;
int dist[N];
int w[S][S];
queue<int>q;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
int pre[S][S],up[S][S];

int get(int x,int y){
    return (x-1)*n+y;
}

void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

int bfs(){
    
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    
    q.push(1);
    
    
    while(q.size()){
        int ver=q.front();
        q.pop();
        
        for(int i=h[ver];~i;i=ne[i]){
            int j=e[i];
            if(dist[j]>dist[ver]+1){
                dist[j]=dist[ver]+1;
                q.push(j);
                // cout<<(j-1)/n+1<<' '<<(j-1)%n+1<<endl;
            }
        }
    }
    return dist[n*n];
}

int main(){
    cin>>n;
    
    for(int i=0;i<=n+5;i++){
        for(int j=0;j<=n+5;j++){
            w[i][j]=1;
        }
    }
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>w[i][j];
        }
    }
    
    memset(h,-1,sizeof h);
    
    for(int i=1;i<=n+1;i++){
        for(int j=1;j<=n+1;j++){
            if(w[i][j]==1){
                pre[i][j]=j;
            }else{
                pre[i][j]=pre[i][j-1];
            }
        }
    }
    
    for(int j=1;j<=n+1;j++){
        for(int i=1;i<=n+1;i++){
            if(w[i][j]==1){
                up[i][j]=i;
            }else{
                up[i][j]=up[i-1][j];
            }
        }
    }
    
    
    for(int i=1;i<=n+1;i++){
        for(int j=1;j<=n+1;j++){
            if(i==n+1&&j==n+1)continue;
            if(w[i][j]==1){
                if(j>=2&&w[i][j-1]==0){
                    add(get(i,j-1),get(i,pre[i][j-1]+1));
                    add(get(i,pre[i][j-1]+1),get(i,j-1));
                }
                if(i>=2&&w[i-1][j]==0){
                    add(get(i-1,j),get(up[i-1][j]+1,j));
                    add(get(up[i-1][j]+1,j),get(i-1,j));
                }
            }
        }
    }
    
    
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(w[i][j]==0){
                for(int k=0;k<4;k++){
                    int a=dx[k]+i,b=dy[k]+j;
                    if(a<1||b<1||a>n||b>n||w[a][b]==1)continue;
                    add(get(i,j),get(a,b));
                    add(get(a,b),get(i,j));
                }
            }
            
        }
    }
    
    int t=bfs();
    
    if(t>0x3f3f3f3f/2)puts("-1");
    else cout<<t;

    
    return 0;
}

~~赛时快些出来了，赛后才写出来qwq~~

题解 | #虫洞操纵者#

虫洞操纵者