【题目来源】
蓝桥云课：1.长草 - 蓝桥云课
【题目描述】
小明有一块空地，他将这块空地划分为 \(n\) 行 \(m\) 列的小块，每行和每列的长度都为 \(1\)。
小明选了其中的一些小块空地，种上了草，其他小块仍然保持是空地。
这些草长得很快，每个月，草都会向外长出一些，如果一个小块种了草，则它将向自己的上、下、左、右四小块空地扩展，
这四小块空地都将变为有草的小块。请告诉小明，\(k\) 个月后空地上哪些地方有草。
【输入】
输入的第一行包含两个整数 \(n,m\)。
接下来 \(n\) 行，每行包含 \(m\) 个字母，表示初始的空地状态，字母之间没有空格。如果为小数点，表示为空地，如果字母为 \(g\)，表示种了草。
接下来包含一个整数 \(k\)。其中，\(2<n,m≤1000,1<k≤1000\)
【输出】
输出 \(n\) 行，每行包含 \(m\) 个字母，表示 \(k\) 个月后空地的状态。如果为小数点，表示为空地，如果字母为 \(g\)，表示长了草。
【输入样例】
4 5
.g...
.....
..g..
.....
2
【输出样例】
gggg.
gggg.
ggggg
.ggg.
【算法标签】
《蓝桥 149 长草》 #2020# #模拟# #省模拟赛# #BFS#
【解题思路】
【代码详解】
# 使用暴力模拟只能过80%（因为是4重循环），改用BFS
n, m = [int(i) for i in input().split()] # 输入n和m
a = [["." for i in range(m)] for i in range(n)] # 初始化a矩阵
queue =[] # 定义队列
for i in range(n): # 输入矩阵ls = input()for j in range(m):a[i][j] = ls[j]if a[i][j]=='g': # 如果某个位置为gqueue.append((i, j)) # 就添加到队列queue中
k = int(input()) # 输入k
dx = [-1, 1, 0, 0] # 定义坐标偏移
dy = [0, 0, -1, 1]def bfs():length = len(queue) # 得到队列长度while length>0: # 当队列不为0（类似C++的q.empty()）tmp = queue.pop(0) # 获取队头元素x, y = tmp[0], tmp[1] # 得到队头元素坐标for i in range(4): # 遍历4个方向xx = x+dx[i]yy = y+dy[i]if xx>=0 and xx<n and yy>=0 and yy<m and a[xx][yy]=='.': # 在范围内，如果是'.'a[xx][yy] = 'g' # 就更新为'g'queue.append((xx, yy)) # 通知将这个坐标添加到队列中，下次循环使用length-=1 # 每次队列长度减1（并不是队列取到空）for i in range(k): # 进行k次bfs遍历bfs()
for i in range(n): # 输出a矩阵for j in range(m):print(a[i][j], end="")print()
【运行结果】
4 5
.g...
.....
..g..
.....
2
gggg.
gggg.
ggggg
.ggg.