长草蓝桥杯模拟赛python解法(BFS)_蓝桥杯长草问题python

题目描述

 解题思路

当遍历周围的所有元素时，我们就要想到用bfs。用到bfs就要用到队列，而且这种遍历周围的也需要构建方向字典。具体看代码注释，注释写的很详细

代码

    from collections import deque
    #输初始化数据
    maps = []
    q = deque()
    direct={(0,1),(1,0),(0,-1),(-1,0)}#草能蔓延的四个方向
 
    #读入数据
    n,m=map(int,input().strip().split())
    for _ in range(n):
        maps.append(list(input()))
    k=int(input())
 
    #遍历maps，如果有草则添加进队列
    for i in range(n):
        for j in range(m):
            if maps[i][j]=='g':
                q.append((i,j))
 
    #bfs广度优先遍历
    def bfs():
        t=len(q)
        #遍历当前队列里所有存储有草的地方
        while t>0:
            temp=q.popleft()
            x,y=temp[0],temp[1]#当前有草的坐标
            for dx,dy in direct:
                #有草的地方像四处蔓延
                nx=x+dx
                ny=y+dy
                if nx>=0 and ny>=0 and nx<n and ny<m and maps[nx][ny]=='.':
                    #判断是否越界或者是否有草
                    #没越界或是空地则添加进队列好下一次遍历并种上草
                    maps[nx][ny]='g'
                    q.append((nx,ny))
            t-=1
 
    #调用bfs的次数，既是长草几个月
    for _ in range(k):
        bfs()
    for i in maps:
        print(''.join(i))