Benjam1n：蓝桥杯2018年第九届真题-迷宫与陷阱（Java代码）

解题思路:
BFS
注意事项:
条件找全
参考代码:

import java.util.*;

public class Main {

	static int N;
	static char[][] map;
	static int K;
	static int step;
	static boolean[][][] vis;
	static int[] dx = { -1, 0, 1, 0 };
	static int[] dy = { 0, -1, 0, 1 };

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		N = in.nextInt();
		K = in.nextInt();
		int ans = -1;
		map = new char[N + 2][N + 2];
		vis = new boolean[N + 2][N + 2][11];
		String tempStr = in.nextLine();
		for (int i = 1; i <= N; i++) {
			tempStr = in.nextLine();
			for (int j = 0; j < tempStr.length(); j++)
				map[i][j + 1] = tempStr.charAt(j);
		}
		Main main = new Main();
		Queue<Node> queue = new LinkedList<Node>();
		queue.offer(map[1][1] == '.' ? main.new Node(1, 1, 0, 0) : main.new Node(1, 1, 0, K));
		if(map[1][1] == '.')
			vis[1][1][0]=true;
		else vis[1][1][K]=true;
		while(!queue.isEmpty()) {
			Node tempNode = queue.poll();
			if(tempNode.x==N&&tempNode.y==N) {
				ans = tempNode.step;
				break;
			}
			for(int i=0;i<4;i++) {
				int x = tempNode.x+dx[i];
				int y = tempNode.y+dy[i];
				if(map[x][y]!='#'&&x>=1&&x<=N&&y>=1&&y<=N) {
					if(map[x][y]=='X'&&tempNode.invincible>0&&vis[x][y][tempNode.invincible-1]==false) {
						vis[x][y][tempNode.invincible-1]=true;
						queue.offer(main.new Node(x,y,tempNode.step+1,tempNode.invincible-1));
					}else if(map[x][y]=='%'&&vis[x][y][K]==false) {
						vis[x][y][K]=true;
						queue.offer(main.new Node(x,y,tempNode.step+1,K));
					}else if(map[x][y]=='.'&&tempNode.invincible==0&&vis[x][y][0]==false) {
						vis[x][y][0]=true;
						queue.offer(main.new Node(x,y,tempNode.step+1,0));
					}else if(map[x][y]=='.'&&tempNode.invincible>0&&vis[x][y][tempNode.invincible-1]==false) {
						vis[x][y][tempNode.invincible-1]=true;
						queue.offer(main.new Node(x,y,tempNode.step+1,tempNode.invincible-1));
					}
				}
			}
		}
		System.out.println(ans);
	}

	class Node {
		int x;
		int y;
		int step;
		int invincible;

		public Node(int x, int y, int step, int invincible) {
			super();
			this.x = x;
			this.y = y;
			this.step = step;
			this.invincible = invincible;
		}
	}
}