刷题 BFS 广度优先算法 : 大胖子走迷宫 （python, java）

刷题 BFS 广度优先算法 : 大胖子走迷宫 （python, java）

https://www.lanqiao.cn/problems/234/learning/
http://lx.lanqiao.cn/problem.page?gpid=T2739#submitpanel

输入输出样例

示例

输入

9 5
+++++++++
+++++++++
+++++++++
+++++++++
+++++++++
***+*****
+++++++++
+++++++++
+++++++++
1
2
3
4
5
6
7
8
9
10

输出

16
1

Python

# 全局变量
map_char = []
visit = []  # 位置状态，

# 方向
dx = [1,-1,0,0]
dy = [0,0,-1,1]


def BFS(queue, n, k, tmp):
    count = 0 # 计时
    while len(queue) !=0:
        size = len(queue)
        
        # 遍历queue 
        while size > 0:
            size -= 1  # 数量-1
            curr = queue.pop(0)  # 当前坐标
            x = curr[0]
            y = curr[1]
            # 结束条件, 因为下标是0开始，所以终点要减1
            if x==n-3 and y==n-3:
                return count
            # 4个行走方向
            for i in range(4):
                a = x+dx[i]
                b = y+dy[i]
                # 判断是否越界，是否访问过，检测是否碰到障碍物
                if check(a,b,n,k,tmp):
                    queue.append([a,b])
                    visit[a][b] = True
            # 因为胖子会缩小，所以阻塞时胖子可以在原地等待
            queue.append([x,y])
        # 增加计时
        count += 1
        # 处理胖子缩小的膨胀因子
        if count == k:
            tmp = 1
        if count == 2*k:
            tmp = 0
    
def check(a,b,n,k,tmp):
    # 判断是否越界，是否访问过，检测是否碰到障碍物
    flag = True
    if a-tmp >= 0 and a+tmp<n and b-tmp>=0 and b+tmp <n and not visit[a][b]:
        flag = True
    else:
        flag = False
    
    # 判断小明占据的大方块里是否有*
    for i in range(a-tmp, a+tmp+1):
        for j in range(b-tmp, b+tmp+1):
            if i>=0 and i<n and j>=0 and j<n and map_char[i][j] == '*':
                flag = False
    return flag

if __name__=="__main__":
    tmp = 2  # 膨胀因子 帮助计算胖子占的大小
    # 输入
    n, k = map(int, input().split(' '))
    # 根据输入初始化地图
    for _ in range(n):
        map_char.append(list(input()))
    # 初始化位置状态，如果已经经过，为False
    visit = [[False for _ in range(n)] for _ in range(n)]
    
    # 初始化bfs队列
    visit[2][2] = True
    queue = [[2,2]]
    # 开始宽度优先搜索
    
    count = BFS(queue=queue,n=n,k=k,tmp=tmp)
    print(count)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

Java

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

public class 大胖子走迷宫 {
	
	static int N=310;  //地图最大值
	static char[][] arr = new char[N][N]; //地图
	static boolean[][] visit = new boolean[N][N];  // 状态
	static int[] dx = {1,-1,0,0};
	static int[] dy = {0,0,-1,1};
	static int tmp=2;  // 膨胀因子为2
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n= scan.nextInt(); // 地图大小
		int k= scan.nextInt();  // 变化时间
		for (int i = 0; i < n; i++) {
			arr[i] = scan.next().toCharArray();
		}
		
		Queue<int[]> queue = new LinkedList<>();
		queue.offer(new int[] {2,2});  // 初始坐标是2,2
		visit[2][2]=true;
		int count=0; //计步数
		while (!queue.isEmpty()) {
			int size = queue.size();
			
			while (size-- > 0) {
				int[] curr = queue.poll();
				int x = curr[0];
				int y = curr[1];
				// 因为坐标是从0开始，所以要减去3
				if (x==n-3&&y==n-3) {
					// 结束条件
					System.out.println(count);
					return;
				}
				// 四个方向
				for (int i = 0; i < 4; i++) {
					int a = x+dx[i];
					int b = y+dy[i];
					// 判断是否越界，是否访问过，检测是否碰到障碍物
					if (a-tmp>=0&&a+tmp<n&& b-tmp>=0&&b+tmp<n && !visit[a][b]&& check(a,b)) {
						queue.offer(new int[]{a,b});
						visit[a][b]=true;
					}
				}
				// 需要把自己当前位置加入队列，表示原地等待
				queue.offer(new int[] {x,y});
			}
			count++;
			// 处理膨胀因子
			if (count==k) {
				tmp=1;
			}
			if (count==2*k) {
				tmp=0;
			}
		}
	}
	// 判断小明占据的大方块里是否有*
	public static boolean check(int a,int b) {
		for (int i = a-tmp; i <= a+tmp; i++) {
			for (int j = b-tmp; j <= b+tmp; j++) {
				if (arr[i][j]=='*') {
					return false;
				}
			}
		}
		return true;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73