Xiao Ming is playing a maze game, in which he controls his character to leave a 2D maze consisting of NxN grids.
Xiao Ming's starting position is in the upper left corner, and he needs to reach the grid in the lower right corner to leave the maze.
At each step, he can move to the adjacent grids up, down, left, and right (provided that the target grid can pass through).
There are some grids in the maze that Xiaoming can pass through, we use '.' to indicate;
Some grids are walls, Xiaoming can't pass through, we use '#' to indicate.
In addition, some grids have traps, which we denote by 'X'. Unless Xiao Ming is invincible, he cannot pass.

There are invincible items on some grids, we use '%' to indicate.
When Xiao Ming reaches the grid for the first time, he will automatically acquire the invincible state, and the invincibility state will last for K steps.
After that, if you reach the grid again, you will no longer be invincible.

When invincible, you can pass through the grid with traps, but the traps will not be dismantled/destroyed, that is, the traps will still prevent characters who are not invincible from passing through.

Given a maze, please calculate that Xiao Ming can leave the maze after at least a few steps

input format

　　----
The first line contains two integers N and K. (1 <= N <= 1000 1 <= K <= 10)
The following N rows contain an NxN matrix.
The matrix guarantees that the upper left and lower right corners are '.'.

output format

　　----
An integer representing the answer. If Xiao Ming cannot leave the maze, output -1.

sample input

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

Sample output

10

sample input

5 1
...XX
##%#.
...#.
.###.
.....

Sample output

12

Ideas for this topic

This question is the deformation of bfs, mainly to grasp two points

One point is that this is a reversible bfs. Passing through invincibility may lead to different routes, so once invincible still exists here, you can return to the original position, but it can't be stopped. The solution here is because invincibility It disappears after being used, and the result after reaching invincibility is certain, so once invincible is used, this position can be marked as a wall

Another point is that this invincibility is not superimposable, it is that after passing the invincible point, there are k remaining before superimposition.

Then this is a dfs deformation, the whole is not very difficult

code below

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.LinkedList;
import java.util.Queue;

public class Main mazes and traps {

	public static void main(String[] args) throws IOException {
		BufferedReader x=new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out=new PrintWriter(System.out);
		String ss[]=x.readLine().split(" ");
		int n=Integer.valueOf(ss[0]),m=Integer.valueOf(ss[1]);
		int aa[][]=new int[n][n];
		for(int i=0;i<n;i++) {
			String s=x.readLine();
			for(int j=0;j<n;j++)
				if(s.charAt(j)=='X')
					aa[i][j]=2;
				else if(s.charAt(j)=='#')
					aa[i][j]=1;
				else if(s.charAt(j)=='%')
					aa[i][j]=3;
		}
		boolean bj[][]=new boolean[n][n];
		Queue<dt> q=new LinkedList<dt>();
		q.add(new dt(0, 0, 0, 0));
		bj[0][0]=true;
		int fx[][]= {{1,0},{0,1},{-1,0},{0,-1}};
		while(!q.isEmpty()) {
			dt d=q.poll();
			if(d.x==n-1&&d.y==n-1) {
				out.println(d.l);
				out.flush();
				return;
			}
			for(int i=0;i<4;i++) {
				int xx=d.x+fx[i][0];
				int yy=d.y+fx[i][1];
				if(xx>=0&&yy>=0&&xx<n&&yy<n&&aa[xx][yy]!=1) {
					if(aa[xx][yy]==3) {
						q.add(new dt(xx,yy,d.l+1,m));
						aa[xx][yy]=1;
					}
					else if(d.wd>0) {
						q.add(new dt(xx,yy,d.l+1,d.wd-1));
						bj[xx][yy]=true;
					}
					else if(aa[xx][yy]==0&&!bj[xx][yy]) {
						q.add(new dt(xx,yy,d.l+1,0));
						bj[xx][yy]=true;
					}
				}
			}
		}
		out.println(-1);
		out.flush();
	}

}
class dt{
	int x;
	int y;
	int l;
	int wd;
	public dt(int x,int y,int l,int wd) {
		this.l=l;
		this.wd=wd;
		this.x=x;
		this.y=y;
	}
}