问题：考虑一名患者患有皮肤感染，细菌正在迅速传播。假设皮肤表面被缩放为大小为MxN的矩形网格，并且单元由0和1标记，其中0表示皮肤上的未受影响区域，1表示皮肤上受影响区域。细菌可以从网格的一个细胞向四个可能的方向(右、左、上、下)移动到另一个细胞，但一次只能向一个方向移动到一个细胞并在1秒内影响该细胞。目前正在治疗患者的医生看到了患者的状态，想知道在细菌扩散到皮肤上并导致患者死亡之前，他还有多少时间来拯救他。你能帮助估计细菌完全占据皮肤表面所需的最短时间吗？
输入：：皮肤的当前状态。(MxN大小的矩阵，具有1和0，表示受影响和未受影响的区域)
输出：：覆盖整个网格的最小时间(以秒为单位)。
示例：
输入：
[1 1 0 0 1]
[0 1 0 0]
[0]0 0 1]
[0]1 0 0]输出：2秒
解释：
输入1秒后，矩阵可能如下
[1 1 1 0 1]
[1 1 1 1 0 1]
[0 1 1 0 1]
[0]1 0 1]在接下来的几秒钟里，矩阵被1的完全填满
我不会在这里介绍详细的解决方案，但一些想法有望帮助您编写自己的程序。
- 第一步是确定要实现的算法类型。最佳方法是为这个问题找到一个简单快速的临时解决方案。在没有这种解决方案的情况下，对于这类问题，经典的候选者是DFS、BFS、a*
由于目标是找到最短的解决方案，因此首先考虑BFS似乎很自然，因为一旦BFS找到解决方案，我们就知道它是最短的，我们可以停止搜索。然而，我们必须考虑避免节点膨胀，因为这不仅会导致巨大的计算时间，还会导致巨大的内存。
- 避免节点膨胀的第一个想法是考虑一些
1细胞只能在另一个细胞中消耗。例如，在张贴的图表中，单元格(0，0)(左上角)只能用于单元格(1，0)。然后，在该扩增之后，细胞(1，1)只能移动到细胞(2，1)。因此，我们知道将单元格(1,1)移动到单元格(1,0)是次优的。因此：先移动这些细胞
以类似的方式，一旦一个受感染的细胞只被其他感染的细胞包围，就不再需要考虑下一步行动。
最后，有一个感染细胞的列表，以及每个这样的细胞可以移动到的未感染细胞的数量，会很方便。
-
限制节点数量的另一个想法是检测重复项，因为在这里可能会存在许多重复项。为此，我们必须定义一种散列。所使用的哈希函数不需要100%高效，但需要快速计算，如果可能的话，还需要以递归方式计算。如果我们通过在位置(i，j)添加一个1-单元格从A图中获得B图，那么我提出了类似的东西
H(B) = H(A)^f(i, j)f(i, j) = a*(1024*i+j)%b
这里，我使用了N和M小于1000的事实。
每次考虑一个新的图表时，我们都必须计算相应的H值，并检查它是否已经存在于过去的图表集中。
我不确定在面试中我能走多远。经过一番思考，我宁愿考虑贪婪的优先级队列，而不是考虑存储多个完整板状态的解决方案，因为下一个要填充的零单元候选者的强启发式似乎是：
(1) 具有最少相邻感染细胞的健康细胞(当然，至少有一个)，
e.g., choose A over B
1 1 B 0 1
0 1 1 0 0
0 0 A 0 1
0 1 0 0 0
和(2)通过首先选择健康细胞来打破联系，所述健康细胞在被感染时将阻断受感染最少的细胞。
e.g., choose A over B
1 1 1 0 1
1 B 1 0 A
0 0 0 0 1
0 1 0 0 0
一个有趣的观察结果是，从技术上讲，任何健康的细胞目的地都可以在曼哈顿距离最近的受感染细胞很远的地方及时到达，在那里，导致这种"爬行"的细胞不断选择让我们更接近目的地的单次移动。然而，我们知道，与此同时，同样受感染的细胞"蛇"会产生新的"爬行器"，可以到达任何同样遥远或更近的邻居。这让我想知道是否有更有效的方法来确定下限，基于最远健康细胞的计数。
这是多智能体寻路问题(MAPF)的一个变体。最近有很多关于这个主题的工作，但早期的现代工作是找到这个问题的最佳解决方案的一个很好的起点，例如算子分解方法。
要做到这一点，你需要对病原体(细菌)1..k进行排序。然后，你需要开始搜索，生成细菌1的所有可能的第一步，然后生成细菌2的所有可能第一步，依此类推，病原体的移动将停留在原地，或传播到相邻的未被占用的位置。每个细菌有4个可能的动作，在完整状态之间有多达4^k个可能的行动。(当你还没有将操作分配给所有k个代理时，就会出现部分状态。)操作的数量是指数级的，这意味着你可能很快就会遇到资源限制(时间或空间)。但是，只有2^(MxN)态是可能的。(由于病原体不会消失，实际上是2^(MxN-i)，其中i是初始细菌的数量。)
每一次所有的(k)细菌都考虑了一个可能的动作，你就有了一个新的完整状态。(然后k在下一次迭代中增加。)剩下的最短时间来自填充了网格的最浅完全状态。一点蛮力计算就能找到最短的解决方案。(在大电网的情况下相当多。)
您可以使用BFS来查找第一个完全填充的状态。但是，A*可能会做得更好。作为一种启发式方法，您可以考虑在每个步骤中填充所有单元格的所有相邻位置，然后计算在该模型下填充网格所需的步骤数。这给出了填充整个网格所需时间的下限。
但是，还有更多的优化。进行算子分解的原因是，你可以先命令动作采取最好的动作，而不考虑较弱的可能性(例如，所有细菌都不会传播)。你也可以使用部分扩展方法(EPEA*)来避免为细菌生成许多明显的次优策略。
如果我把这个问题作为面试问题来问，我可能会看到有人提出问题(什么是行动，什么是状态)，提出解决方案的下限(每个细菌都扩展到每个相邻的细胞)，提出算法，也许会按照难度增加的顺序分析问题的难度。