给定一个矩阵大小为NxM的0和1。如果鼠标出现在[i:j]处，则它将是1，否则它将是0。我们必须从[0:0]开始并达到[n-1:m-1]。我们只能向下或向右走。如果我们经过一个[i:j]位置，那么[x:y]位置的鼠标会吓到我们。
找到一条我们被最少数量的老鼠吓坏的路。记住“与众不同”这个词，即老鼠如果吓到我们，它就不会再吓到我们了。
这个问题是在一次采访中提出的我试图用一般的DP问题中的思想来解决这个问题，我们可以向下和向右移动，并且必须找到最小路径，但是在所有这些问题中，我们可以采用最小值|i-x|+|j-y|<=1和[i-1:j]来找到当前索引最小值，并从左到右向下处理所有行。
但我不能在这里使用这个想法，因为这里一只老鼠影响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