Here I will write out the important thinking part of solving the problem , You can browse the code first , If you don't understand, focus on the analysis process .

The fat man walks the maze

link : The fat man walks the maze .

This kind of maze problem is a typical application BFS Example of template

First , And DFS similar ,BFS The function of is to enumerate all cases , Until we find the solution we need . and BFS It depends on the queue , Put the elements with the same priority into the queue and cycle with the same priority , Add the next priority , Until we find the situation we want .

Next , Let's solve the problem in detail .

The general idea of solving the problem

Get this kind of maze topic , We can roughly decide to use BFS Template to solve the problem

BFS Limiting conditions

Since the use of BFS, We definitely can't repeat the search The same situation , Otherwise, it will fall into a dead cycle . Be careful , What we say The same situation and Not in the same position , But an additional state of reaching this position . This condition will be reflected in the following question .

Xiao Ming wants to go from the beginning to the end , Each step must meet several conditions ：

• The current coordinates , Add Xiao Ming's current weight （ Width ）, Will it cross the line ？
• Whether there will be... Around Xiaoming's next station ‘#’ obstacle ？

The code implementation part of the legalization judgment for these two coordinates is as follows ：
among xx,yy Respectively represent the horizontal and vertical coordinates to judge whether you can walk next
check The function is to check whether there are obstacles blocking the way

    if(xx-len>=0&&xx+len<n&&yy-len>=0&&yy+len<n&&!visit[xx][yy]&&check(xx,yy)) {
    
        			
        		}

public static boolean check(int x,int y) {
    
			for(int i=x-len;i<=x+len;i++) {
    
				for(int j=y-len;j<=y+len;j++) {
    
					if(map[i][j] == '*')
						return false;
				}
			}
		
		return true;
	}

Termination conditions

As long as the current position coordinates reach the end point , I can output the result , The program is over ：

        if(cur[0] == n-3&&cur[1] == n-3) {
    
        		System.out.println(time);
        		return;
        	}

The choice of path

The choice of path is mainly based on the judgment of the four directions of the current position , If you can go , We'll join the team .

however , We should pay special attention to this problem ： Xiao Ming's width will change . in other words , Maybe in a while , After the width of Xiaoming decreases, a new path will appear at the current position . With that in mind , Before Xiaoming's volume reaches the minimum , We all have to put our current position in the team .

for(int c=0;c<size;c++) {
    
        		int[] cur = queue.poll();
        	    if(cur[0] == n-3&&cur[1] == n-3) {
    
        		System.out.println(time);
        		return;
        	}
        		for(int i =0;i<4;i++) {
    
        		int xx = cur[0] + dx[i];
        		int yy = cur[1] + dy[i];
        		if(xx-len>=0&&xx+len<n&&yy-len>=0&&yy+len<n&&!visit[xx][yy]&&check(xx,yy)) {
    
        			queue.offer(new int[] {
    xx,yy});
        			visit[xx][yy] = true;
        		}
        	}
        	if(len!=0)
        	queue.offer(new int[] {
    cur[0],cur[1]});
        	}

The increase in time

Because we use size The same priority is recorded （ Time ） Path through , In each round size Add time after completion , Change Xiaoming's weight

            time++;
        	
        	if(time==k)  len=1;
        	if(time == 2*k) len=0;

The overall code

import java.util.*;

public class  The fat man walks the maze  {
    
    public static char[][] map;
    public static int[] dx = {
    -1,0,1,0};
    public static int[] dy = {
    0,-1,0,1};
    public static int n,k,len=2;
    public static boolean[][] visit;
	public static void main(String[] args) {
    
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		k = sc.nextInt();
		visit = new boolean[n][n];
		map = new char[n][n];
		for(int i=0;i<n;i++) {
    
			map[i] = sc.next().toCharArray();
		}
		Queue<int[]> queue = new LinkedList<>();
		queue.offer(new int[] {
    2,2});
		visit[2][2] = true;
		int time = 0;
        while(!queue.isEmpty()) {
    
        	int size = queue.size();
        	
        	for(int c=0;c<size;c++) {
    
        		int[] cur = queue.poll();
        	    if(cur[0] == n-3&&cur[1] == n-3) {
    
        		System.out.println(time);
        		return;
        	}
        		for(int i =0;i<4;i++) {
    
        		int xx = cur[0] + dx[i];
        		int yy = cur[1] + dy[i];
        		if(xx-len>=0&&xx+len<n&&yy-len>=0&&yy+len<n&&!visit[xx][yy]&&check(xx,yy)) {
    
        			queue.offer(new int[] {
    xx,yy});
        			visit[xx][yy] = true;
        		}
        	}
        	if(len!=0)
        	queue.offer(new int[] {
    cur[0],cur[1]});
        	}
        	time++;
        	
        	if(time==k)  len=1;
        	if(time == 2*k) len=0;
        }
        
	}
	
	public static boolean check(int x,int y) {
    
			for(int i=x-len;i<=x+len;i++) {
    
				for(int j=y-len;j<=y+len;j++) {
    
					if(map[i][j] == '*')
						return false;
				}
			}
		
		return true;
	}

}

Mazes and traps

link : Mazes and traps .

The restrictions here have obviously increased , We followed the general idea of the above question and ran away 40 branch

It's really not easy to change , It's still the national title , Let's put the timeout code first

The overall code

import java.util.*;
public class Main {
    
	
	public static int N,K;
	public static boolean[][] visit;
	public static char[][] map;
	public static int[] dx = {
    0,1,-1,0},dy = {
    1,0,0,-1};
	public static void main(String[] args) {
    
		// TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        K = sc.nextInt();
        map = new char[N][N];
        for(int i =0;i<N;i++) {
    
        	map[i] = sc.next().toCharArray();
        }
        int time = 0;
        Queue<int[]> queue = new LinkedList<>();
        int w = map[0][0]=='%'?K:0;
        queue.offer(new int[] {
    0,0,w});
        while(!queue.isEmpty()) {
    
        	int size = queue.size();
        	for(int c = 0;c<size;c++) {
    
        		int[] cur = queue.poll();
        		if(cur[0]==N-1&&cur[1]==N-1) {
    
        			System.out.println(time);
        			return;
        		}
        		for(int i =0;i<4;i++) {
    
        			int xx = cur[0] +dx[i];
        			int yy = cur[1] +dy[i];
        			if(xx>=0&&xx<N&&yy>=0&&yy<N&&check(xx,yy,cur[2])) {
    
        				w=cur[2]>0?cur[2]-1:0;
        				if(map[xx][yy]=='%')
        					w+=K;
        				queue.offer(new int[] {
    xx,yy,w});
        			}
        		}
        	}
        	time++;
        }
        
        
	}
	
	public static boolean check(int x,int y,int w) {
    
		if(map[x][y]=='#'||map[x][y] == 'X'&&w<=0)
			return false;
		return true;
	}

}