【算法】Python-BFS循环解法

🏓引入

题目引子

在给定网格里，每个单元格有着以下三个值之一：

• 值0代表空块；
• 值1代表正常块；
• 值2代表异常块。

每单位时间，与异常块上下左右四个方向上相邻的正常块都会被影响，变成异常块。

请返回直到单元格中没有正常块为止所必须经过的最短时间，若最后一定会剩下正常块，则返回-1。

例1：

in : [[2,1,1],[1,1,0],[1,0,1]]
out: 4

例2：

in : [[2,1,1],[0,1,1],[1,0,1]]
out: -1

其中，网格的长宽最大值为10

概念引入

BFS（Breadth First Search），即广度优先算法。这个是对于图的一种算法，可以用来求最短路径。对于一个图$G=(V,E)$和一个源顶点$s$，从$s$开始，按照$G$的宽度来盲目搜索节点，若发现目标则终止，它并不考虑结果的可能位置，而是彻底地搜索整张图。

定义若是过于抽象，可以通过下面的代码来理解：

---

🌟思考过程