蓝桥杯2019年第十届国赛真题-大胖子走迷宫

解题思路:

注意事项: 这个题和一般的迷宫问题不同在于可以呆在原地等待，vis[][]用于记录走过的位置，注意原地等待不用判断是否走过（因为一定已经走过）

参考代码:

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class 大胖子走迷宫 {
   static int[] xx ={1,0,-1,0};
   static int[] yy ={0,1,0,-1};
   static boolean[][] vis;
   public static void main(String[] args) {
       Scanner scanner = new Scanner(System.in);
       int n = scanner.nextInt();
       int k = scanner.nextInt();
       char[][] map = new char[n + 2][n + 2];
       vis = new boolean[n + 2][n + 2];
       for (int i = 1; i <= n; i++) {
           String str = scanner.next();
           for (int j = 1; j <= n; j++) {
               map[i][j] = str.charAt(j - 1);
           }
       }
       System.out.println(bfs(map,k,n));
   }
   public static int bfs(char[][]map,int k,int n){
       Queue<int []> queue=new LinkedList<>();
       queue.add(new int[]{3,3,0});
       while (!queue.isEmpty()){
           int[] now =queue.poll();
           if(now[0]==n-2&&now[1]==n-2){
               return now[2];
           }
           for(int i=0;i<=3;i++){
               int dx=xx[i]+now[0];
               int dy=yy[i]+now[1];
               if(now[2]<k){
                   if(dx<=n-2&&dx>=3&&dy>=3&&dy<=n-2&&!vis[dx][dy]){
                       boolean can=true;
                       for(int j=dx-2;j<=dx+2;j++){
                           for(int p=dy-2;p<=dy+2;p++){
                               if(map[j][p]=='*')
                               {
                                   can=false;
                                   break;
                               }
                           }
                       }
                       if(can)
                       {
                           vis[dx][dy]=true;
                           queue.add(new int[]{dx,dy,now[2]+1});
                       }
                   }
               }
               else if(now[2]<2*k&&now[2]>=k){
                   if(dx<=n-1&&dx>=2&&dy>=2&&dy<=n-1&&!vis[dx][dy]){
                       boolean can=true;
                       for(int j=dx-1;j<=dx+1;j++){
                           for(int p=dy-1;p<=dy+1;p++){
                               if(map[j][p]=='*')
                               {
                                   can=false;
                                   break;
                               }
                           }
                       }
                       if(can)
                       {
                           vis[dx][dy]=true;
                           queue.add(new int[]{dx,dy,now[2]+1});
                       }
                   }
               }
               else {
                   if(dx<=n&&dx>=1&&dy>=1&&dy<=n&&!vis[dx][dy]){
                       if(map[dx][dy]!='*')
                       {
                           vis[dx][dy]=true;
                           queue.add(new int[]{dx,dy,now[2]+1});
                       }
                   }
               }
           }
           queue.add(new int[]{now[0],now[1],now[2]+1}); //增加原地等待选项
       }
       return -1;
   }
}