algorithm - 动态规划算法

Question

给定一个大小为 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 个细胞。

谁能告诉我如何解决这个问题？

Answer 1

我认为解决这个问题的最简单(不够有效)的方法是解决 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