给定一个大小NxM为0和的矩阵1。如果鼠标存在，[i:j]那么它会存在1，否则它会存在0。我们必须从 开始[0:0]并到达[n-1:m-1]。我们只能向下或向右。[i:j]如果我们通过[x:y]这样的位置，鼠标在某个位置会吓到我们|i-x|+|j-y|<=1。
找到一条我们被最少数量的不同老鼠吓到的路径。请注意“不同”这个词，即老鼠如果吓到了我们，那么它就不会再吓到我们了。
这个问题是在一次采访中被问到的。我试图通过一般 DP 问题中使用的想法来解决它，我们可以向下和向右移动并且必须找到最小路径，但是在所有这些问题中，我们可以取最小值[i-1:j]并[i:j-1]找到当前索引最小值并处理所有行从左到右。
但我不能在这里使用这个想法，因为这里的鼠标影响 4 个细胞。
有人可以给出如何解决这个问题的想法吗？
我认为解决这个问题的最简单（不够有效）的方法是解决 NxM 顶点图上的最短路径，使用以下边成本函数（i 和 j 是指单元格的图节点（i'，j'）和 (i'',j'') 在主矩阵中）：
c(i,j) = 1 if [(i',j') and (i'',j'') are sideByside] && [(i'',j'') is scaring] ,
0 otherwise
我认为非常简单的想法（可能不完整，但足以让面试官满意）如下。
我们为边分配权重。首先，所有边的权重为 0。然后考虑顶点 A 中的鼠标。顶点 A 有 4 个相邻边 b、c、d、e，它们将 A 与顶点 B、C、D、E 连接起来（A 只有 2 或3 个相邻边相似）。因此，现在我们将与顶点 B、C、D、E 相邻的每条边的权重增加 1，但边 b、c、d、e 除外。现在顶点 A 将权重 2 添加到“被顶点 A 吓到”的每个 MINIMAL 权重路径。任何可能的 4 角鼠标都需要特别考虑，我们可以将边缘权重增加 2。
现在我们有一个最简单的 DP 问题，即在整数格中找到一条具有向下/向右移动的最小权重路径。我担心的是只用 1 或 2 个步骤分开的老鼠。我很快检查了一下，这似乎可行，但我没有完整的证明。
在每个单元格中，存储最有效路径的来源（顶部或左侧）（本质上是每个单元格的位值）。
当考虑左侧的单元格时，如果该单元格来自顶部并且当前单元格的正上方有一只鼠标，我们知道它已经吓到了我们。
插图：（C是当前单元格，L在左边，S是源L）
0S1 <- this mouse already scared us
0LC
当考虑到顶部的单元格时，如果该单元格来自左侧并且当前单元格的左侧有一只鼠标，我们知道它已经吓到了我们。
插图：（C是当前单元格，T是到顶部，S是源T）
0ST
01C
^- this mouse already scared us
当考虑到顶部的单元格时，如果那个单元格有一只老鼠，我们知道它已经吓到我们了。
插图：（C是当前单元格）
01 <- this mouse already scared us
0C
当考虑左边的单元格时，如果那个单元格有一只老鼠，我们知道它已经吓到我们了。
插图：（C是当前单元格）
01C
^- this mouse already scared us
在考虑顶部或左侧的单元格时，如果当前单元格有鼠标，我们知道它已经吓到了我们。
插图：（1是当前单元格，L在左侧，T在顶部）
0T
L1 <- this mouse already scared us
从这里推导出算法应该不会太难。
如果我们只是在穿过它的细胞时被老鼠吓到，那么问题将是微不足道的。如果它通过其中一个鼠标细胞，只需增加路径的恐怖度。通过对路径的归纳，我们可以记住从给定单元到终点的最佳路径，然后以通常的 DP 方式构建到达起点的路径。
复杂性是由以下要求创建的：如果我们通过鼠标范围内的 5 个单元之一，那么我们需要增加路径的恐怖度，但只需要增加一次。
这可以通过使用宽度为 N 的位字段来实现，其中 N 是鼠标的数量，第 i 位指示路径是否会导致您害怕第 i 个鼠标。然后，DP 可以对一个向量 (0,0,..,0,1,0,..,0,0) 使用按位或运算，其中 1 位于第 i 个鼠标的第 i 个位置。
但是你在找到最佳部分路径时会遇到问题，因为没有严格的相同权重的位域排序。一些简单的启发式逻辑表明，您只需要关注鼠标周围不超过 9 个细胞的区域的区别。因此，您可以简单地跟踪附近的一组最佳部分路径。靠近鼠标 i 的解决方案是不被鼠标 i 吓到的最佳解决方案，以及被鼠标 i 吓到的解决方案。离开接近度后，区分两者不再相关。