题解 | #虫洞操纵者#java版本

/*

最典型的bfs板子题，最困惑的点就是虫洞如何进行操作，我们直接对每个点进行爆搜即可， 四个方向需要进行分类讨论，因为他们最终的落点不相同，

着重注意的几个点：

1、数组我们要开n+2个，因为迷宫被墙包围，我们多开数组并把他们全部预处理为墙“1”

2、标记数组直接用来存储结果，所以我们不使用布尔数组来记录，简化代码

*/

import java.util.*;

public class Main{

static int n;
public static void main(String args[]){
    Scanner sc=new Scanner(System.in);
     n=sc.nextInt();
    int map[][]=new int[n+2][n+2];
    for(int i=1;i<= n;i++){
        for(int j=1; j<= n; j++){
            map[i][j]=sc.nextInt();
        }
    }
    for (int i = 0; i < n+2; i++) {
    //此处是在进行最外面的墙的预输入
        map[0][i]=1; map[n+1][i]=1;
        map[i][0]=1; map[i][n+1]=1;
    }
    int vis[][]=new int[n+2][n+2];
    //直接使用标记数组vis来记录数值
    for (int i = 0; i < n+2; i++) {
        for (int j = 0; j < n+2; j++) {
            vis[i][j]=-1;
        }
    }
    System.out.println(bfs(map,vis));
}
public static int bfs(int map[][] , int vis[][]){
    int dx[]=new int[]{0, 0,1,-1};
    int dy[]=new int[]{1,-1,0,0};
    Queue<int[]> q=new LinkedList<>();
    q.add(new int[]{1,1});
    vis[1][1]=0;
    //因为数组开大要存边界的墙，所以出发点是（1,1）
    while(!q.isEmpty()){
        int cur[]=new int[2];
        cur=q.poll();
        int x=cur[0];
        int y=cur[1];
        for (int i = 0; i < 4; i++) {
            int xx=x+dx[i],yy=y+dy[i];
            if (xx < 0 || xx >= n + 2 || yy < 0 || yy >= n + 2) continue;
            if(vis[xx][yy]!=-1) continue;
            //接下来的四个判断语句用来进行虫洞的穿越
            if(map[xx][yy]==1){//碰到墙了，开始进行虫洞的穿越
                if(i==0){
                    for (int j = y; j >= 0; j--) {
                        if(map[xx][j]==1){
                            xx=x; yy=j+1;
                            break;
                        }
                    }
                }
                else if(i==1){
                    for (int j = y; j < n+2; j++) {
                        if(map[xx][j]==1){
                            xx=x; yy=j-1;
                            break;
                        }
                    }
                }
                else if(i==2){
                    for (int j = x; j >=0 ; j--) {
                        if(map[j][yy]==1){
                            yy=y;xx=j+1;
                            break;
                        }
                    }
                }
                else {
                    for (int j = x; j < n+2 ; j++) {
                        if(map[j][yy]==1){
                            yy=y;xx=j-1;
                            break;
                        }
                    }
                }
                //如果vis的值不是-1，证明这个点已经被访问过，直接打断即可
                if(vis[xx][yy]!=-1) continue;
                //此处我们要继承上一个点的值，所以有很多人想到了dp
                vis[xx][yy]=vis[x][y]+1;
                q.add(new int[]{xx,yy});

            } else{//移动的时候没有碰到墙，正常移动进行+1
                vis[xx][yy]=vis[x][y]+1;
                q.add(new int[]{xx,yy});
            }
        }

    }
    return vis[n][n];
}

}