迷宫与陷阱

题目描述

小明在玩一款迷宫游戏，在游戏中他要控制自己的角色离开一间由NxN个格子组成的2D迷宫。
小明的起始位置在左上角，他需要到达右下角的格子才能离开迷宫。
每一步，他可以移动到上下左右相邻的格子中（前提是目标格子可以经过）。
迷宫中有些格子小明可以经过，我们用’.‘表示；
有些格子是墙壁，小明不能经过，我们用’#‘表示。
此外，有些格子上有陷阱，我们用’X’表示。除非小明处于无敌状态，否则不能经过。
有些格子上有无敌道具，我们用’%‘表示。
当小明第一次到达该格子时，自动获得无敌状态，无敌状态会持续K步。
之后如果再次到达该格子不会获得无敌状态了。
处于无敌状态时，可以经过有陷阱的格子，但是不会拆除/毁坏陷阱，即陷阱仍会阻止没有无敌状态的角色经过。
给定迷宫，请你计算小明最少经过几步可以离开迷宫

输入

输入包含多组测试数据，对于每组测试数据：
第一行包含两个整数N和K。 (1 <= N <= 1000 1 <= K <= 10)
以下N行包含一个NxN的矩阵。矩阵保证左上角和右下角是’.’。

输出

对于每组测试数据输出一行包含一个整数表示答案。
如果小明不能离开迷宫，输出-1。

样例输入

5 3
...XX
##%#.
...#.
.###.
.....

样例输出

10

思路

本来看起来是一道很常规的BFS 但是这里存在一个无敌状态 以前是用二维数组保存走过的记录不再走，这里考虑使用三维数组来保存在无敌k时刻和不无敌的时候走过的记录。

代码

import java.util.LinkedList;
import java.util.Scanner;

public class 蓝桥杯国赛迷宫与陷阱 {
 
    static LinkedList<Node> mylist = new LinkedList<>();
    static int[] r ={1,0,-1,0};
    static int[] c ={0,1,0,-1};
    static int visited[][][] =new int[1010][1010][12];
    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);
        int N =sc.nextInt();
        int K =sc.nextInt();
        char[][] graph = new char[N][N];
        for(int i=0;i<N;i++){
            graph[i]=sc.next().toCharArray();
        }
        sc.close();
        mylist.add(new Node(0, 0, 0, 0));
        visited[0][0][0]=1;
        int result =bfs(N, K, graph);
        System.out.println(result);
        
    }
  
    static int bfs(int N,int K,char[][] graph){
       while(!mylist.isEmpty()){
           Node mynode=mylist.removeFirst();
           if(mynode.x==N-1&&mynode.y==N-1){
           return mynode.bushu;
           }
           for(int i=0;i<4;i++){
               int x1=mynode.x+r[i];
               int y1=mynode.y+c[i];
               int k1=mynode.k;
               int steps = mynode.bushu;
               if(x1<0||x1>=N||y1<0||y1>=N||graph[x1][y1]=='#') continue;
                if(graph[x1][y1]=='%'){
                    visited[x1][y1][K]=1;
                    mylist.add(new Node(x1, y1, steps+1, K));
                }else{
                    if(k1>0&&visited[x1][y1][k1-1]!=1){
                        visited[x1][y1][k1-1]=1;
                        mylist.add(new Node(x1, y1, steps+1, k1-1));
                    }else if(k1==0&&graph[x1][y1]=='.'&&visited[x1][y1][0]!=1){
                        visited[x1][y1][0]=1;
                        mylist.add(new Node(x1, y1, steps+1, 0));
                    }
                }
           }  
       }
       return -1;
       
    }
    static class Node{
        int x,y;
        int bushu;
        int k;
       public Node(int x,int y,int bushu,int k){
            this.x=x;
            this.y=y;
            this.bushu=bushu;
            this.k=k;
        }
    }
}