蓝桥杯 扩散【第十一届】【决赛】【B组】 【Python】 多源点BFS+deque双向队列优化_4个点扩散2020分钟

题目

分析

给出四个点求经过2020分钟后扩散成几个点了，以点为中心向四周扩散的话容易想到是要使用BFS实现。=》多源点BFS

• 本题的难点是如何才能更优的存储、使用数据。如果在考场上跑了几分钟还没出结果是很影响心态的！！！！ 一定要会提升效率

这篇文章分析几种数据类型使用的很棒

通过比较我们发现，不同的数据类型它的处理速度是不一样的。
在队列模型中，最快的是deque双向队列，其次是列表，最后是queue单向队列，没想到列表不是最慢的。

如果要进行数据存储的话集合是最快的，其次是字典，最后时列表，所以进行数据存储的话不要再使用列表啦！（更正：涉及数据查找时不要在列表里面查找）

根据以上结论，以后的BFS要使用deque+集合（判断是否访问过）（如果需要记录路径就用字典）的形式进行计算。

• 另外，本题为了实现当2020分钟后，退出搜索，我们不妨为入队的每一个坐标绑定一个新的属性，记录该点是第几分钟被染色的，（0，0，0） （0，0）坐标是0分钟染色的，当第三位>=2020 就退出搜索

代码

import collections

d=[(1,0),(-1,0),(0,1),(0,-1)]
 
pre={(0,0):(0,0),(2020, 11):(2020,11),(11, 14):(11, 14),(2000, 2000):(2000, 2000)}#初始状态，自己是自己的前节点，本题不用保存路径，完全可以用set
ans=4#已经有4个为黑色
queue=collections.deque()
queue.append((0,0,0))#为入队列的坐标新增一个属性，记录当前是第几分钟被染色的！！！！
queue.append((2020, 11, 0))
queue.append((11, 14, 0))
queue.append((2000, 2000, 0))
 
while queue:
    t=queue.popleft()
    if t[2]>=2020:
        print(ans)
        break
    else:
        for i in d:
            nx,ny=t[0]+i[0],t[1]+i[1]
            if (nx,ny) not in pre.keys() :#题目说画布是无限大的，没有边界问题
                queue.append((nx,ny,t[2]+1))
                pre[(nx,ny)]=(t[0],t[1])
                ans+=1#记录被染色的个数
#扩散 20312088
                

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