这里我会把解题的重要思考部分部分写出来，大家可以先浏览代码，看不懂的地方再重点看分析过程。
大胖子走迷宫
链接: 大胖子走迷宫.
这种走迷宫类题目就是典型的套用BFS模板的例题
首先，与DFS类似，BFS的作用就是枚举所有情况，直到找到我们所需要的解。而BFS是依托队列进行的，将优先级相同的元素放入到队列中进行同一优先级的循环，再加入下一优先级，直到找到我们所要的情况。
接下来，我们具体到题目中来解决问题。
解决题目的大体思路
拿到这类迷宫类的题目，我们大致就可以定下使用BFS的模板来解决题目了
BFS限制条件
既然使用BFS，我们肯定不能重复搜索同一种情况，否则会陷入死循环。注意，我们所说的同一种情况并不是说同一位置，而是到达这一位置的附加状态。这一条件在下题会有所体现。
这题小明想要从起点走到终点，每一步就要满足几个条件：
- 当前的坐标，加上小明现在的重量（宽度），是否会越界？
- 小明下一步的站位周围是否会有‘#’障碍物？
针对这两个坐标合法化判断的代码实现部分如下：
其中xx,yy分别表示接下来要判断是否可以走的横纵坐标
check函数是检查是否有障碍物会挡住去路
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;
}
终止条件
只要当前位置坐标到达了终点，就可以输出结果，结束程序了：
if(cur[0] == n-3&&cur[1] == n-3) {
System.out.println(time);
return;
}
路径的选择
路径的选择主要通过对当前位置的上下左右四个方位的判断，如果可以走，我们就入队。
但是，这题我们尤其要注意：小明的宽度是会变化的。也就是说，可能过一段时间，小明宽度减小后当前位置会出现新的路径。考虑到这点，在小明的体积没有达到最小前，我们都要将当前位置入队。
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]});
}
时间的增加
由于我们用size记录了同一优先级（时间）经过的路径，在每轮size结束后增加时间，更改小明体重即可
time++;
if(time==k) len=1;
if(time == 2*k) len=0;
整体代码
import java.util.*;
public class 大胖子走迷宫 {
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;
}
}
迷宫与陷阱
链接: 迷宫与陷阱.
这里的限制条件明显增多了，我们按上题的大体思路就跑了40分
着实不太好改，还是国赛题目，我们就先放上超时代码了
整体代码
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;
}
}