这种题应该不是Python组的吧,跑了跑其他人的题解发现最后一组解都会超时,权当抛砖引玉了吧。
题目地址:长草
先上BFS模板:
def Bfs(参数):
while quene: # 空?
cur = quene.pop(0) # 弹出队列第一项
for code in code周围结点:
if 符合条件:
代码段
else:
return
先输入数据: 注意在输入grand数组时要转为list形式,因为字符串形式不可变类型,容易导致:
TypeError ‘str‘ object does not support item assignment
n, m = map(int, input().split())
grand = []
for i in range(n):
grand.append(list(input()))
month = int(input())
我们再通过两个for循环找到刚开始有草的左边并把其添加到我们的队列中:
for i in range(n):
for j in range(m):
if grand[i][j] == 'g':
quene.append([i, j])
套用模板:注意我们要用length来表示每个月的生长情况,刚开始length=len(quene),是代表第一个月要向周围生长的草的个数,若一味的套用模板,采用while queue: 的情况下你会发现最终答案是全部长满了草,因为我们最后是要往队列内不断添加草的坐标,若以上述写的话会导致只用一次while就把grand内的空地全变成草了。
def BFS():
length = len(quene)
while length > 0:
length -= 1
x, y = quene.pop(0)
for i in range(4):
dx = x + move[i][0]
dy = y + move[i][1]
if dx >= 0 and dx < n and dy >= 0 and dy < m and grand[dx][dy] == '.':
grand[dx][dy] = 'g'
quene.append([dx, dy])
最后简单补充一下,80%AC代码:
n, m = map(int, input().split())
grand = []
for i in range(n):
grand.append(list(input()))
month = int(input())
move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
quene = []
def BFS():
length = len(quene)
while length > 0:
length -= 1
x, y = quene.pop(0)
for i in range(4):
dx = x + move[i][0]
dy = y + move[i][1]
if dx >= 0 and dx < n and dy >= 0 and dy < m and grand[dx][dy] == '.':
grand[dx][dy] = 'g'
quene.append([dx, dy])
for i in range(n):
for j in range(m):
if grand[i][j] == 'g':
quene.append([i, j])
for i in range(month):
BFS()
for i in range(n):
print(''.join(grand[i]))