给定一个大小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 个细胞。
有人可以给出如何解决这个问题的想法吗?