3

给定一个大小NxM0和的矩阵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 个细胞。

有人可以给出如何解决这个问题的想法吗?

4

4 回答 4

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
于 2013-06-09T07:33:47.690 回答
1

我认为非常简单的想法(可能不完整,但足以让面试官满意)如下。

我们为边分配权重。首先,所有边的权重为 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 个步骤分开的老鼠。我很快检查了一下,这似乎可行,但我没有完整的证明。

于 2013-12-29T19:53:52.607 回答
0

在每个单元格中,存储最有效路径的来源(顶部或左侧)(本质上是每个单元格的位值)。

  1. 当考虑左侧的单元格时,如果该单元格来自顶部并且当前单元格的正上方有一只鼠标,我们知道它已经吓到了我们。

    插图:(C是当前单元格,L在左边,S是源L

    0S1 <- this mouse already scared us
    0LC
    
  2. 当考虑到顶部的单元格时,如果该单元格来自左侧并且当前单元格的左侧有一只鼠标,我们知道它已经吓到了我们。

    插图:(C是当前单元格,T是到顶部,S是源T

    0ST
    01C
     ^- this mouse already scared us
    
  3. 当考虑到顶部的单元格时,如果那个单元格有一只老鼠,我们知道它已经吓到我们了。

    插图:(C是当前单元格)

    01 <- this mouse already scared us
    0C
    
  4. 当考虑左边的单元格时,如果那个单元格有一只老鼠,我们知道它已经吓到我们了。

    插图:(C是当前单元格)

    01C
     ^- this mouse already scared us
    
  5. 在考虑顶部或左侧的单元格时,如果当前单元格有鼠标,我们知道它已经吓到了我们。

    插图:(1是当前单元格,L在左侧,T在顶部)

    0T
    L1 <- this mouse already scared us
    

从这里推导出算法应该不会太难。

于 2013-06-09T11:43:19.367 回答
0

如果我们只是在穿过它的细胞时被老鼠吓到,那么问题将是微不足道的。如果它通过其中一个鼠标细胞,只需增加路径的恐怖度。通过对路径的归纳,我们可以记住从给定单元到终点的最佳路径,然后以通常的 DP 方式构建到达起点的路径。

复杂性是由以下要求创建的:如果我们通过鼠标范围内的 5 个单元之一,那么我们需要增加路径的恐怖度,但只需要增加一次。

这可以通过使用宽度为 N 的位字段来实现,其中 N 是鼠标的数量,第 i 位指示路径是否会导致您害怕第 i 个鼠标。然后,DP 可以对一个向量 (0,0,..,0,1,0,..,0,0) 使用按位或运算,其中 1 位于第 i 个鼠标的第 i 个位置。

但是你在找到最佳部分路径时会遇到问题,因为没有严格的相同权重的位域排序。一些简单的启发式逻辑表明,您只需要关注鼠标周围不超过 9 个细胞的区域的区别。因此,您可以简单地跟踪附近的一组最佳部分路径。靠近鼠标 i 的解决方案是不被鼠标 i 吓到的最佳解决方案,以及被鼠标 i 吓到的解决方案。离开接近度后,区分两者不再相关。

于 2013-06-09T15:24:09.120 回答