有趣的迷宫

Question

我们有一个迷宫R，X，C，其中1<=R，C<=500。这个迷宫由-1到100之间的数字填充。现在，游戏内容如下：

无论哪里有-1方格，假设那是那个单元格中的一块石头块，你就不能穿过那个单元格。您可以从第一列上的任何单元格(当然没有-1)开始，并从最后一列的任何单元格中退出。你可以上下移动，对。当你移动的时候，你在细胞里收集数字，除了-1，它表示一个巨大的石头被放置在我们的迷宫中。每个牢房只能访问一次。

从左到右的路径是什么，您可以选择数字的最大和？放轻松!！Dp会变魔术但是..。这是第五条规则。

如果我们能到达第一排或最底层，我们就能走出迷宫。但接下来有两件事发生： ( a)我们失去了到目前为止收集到的所有积分。 ( b)我们在同一柱状，但在相反的细胞中租用迷宫。

例:考虑3X3迷宫(1 -indexed)。因此，如果我们到达，(1,2)我们可以离开那里，失去所有的积分，进入(3,2)，游戏继续.

现在，我们必须找到有最大分数的路径。

我看不出我们如何通过动态规划来捕捉这个跳出和返回迷宫的过程？而且，我们每次做这件事时都要得分'0‘。

例子：

考虑一下迷宫：

-1  4  5  1
 2 -1  2  4
 3  3 -1 -1
 4  2  1  2

答案=16。

(4,1) -> (4,2) -> (1,2) -> (1,3) -> (2,3) -> (2,4) -> (1,4)

Answer 1

运行与您相同的DP算法。完成一列后，检查顶部/较低位置是否是可访问的(有一条通往那里的路径，并且它们没有被阻塞)。

如果其中一个是可访问的，而另一个不是假设的，那么您可以得到前面分数为0的不可访问的单元格(基本上，再次运行计算，但假设前一列上的单元格得分为0)。

如果没有人可以访问，那就没什么可做的了。

如果两者都是可访问的，因为你在任何地方都有积极的分数，那么做掉一些>0的东西，然后再从0开始是没有意义的。

Answer 2

您应该能够从

A) Left -> Right
B) Top -> Right
C) Bottom -> Right

然后，您还应该能够从(没有-1)获得一个路径列表。

D) Left -> Top
E) Left -> Bottom

从列表(B)中删除列表(D)中没有连接路径的任何内容。从列表(C)中删除列表(E)中没有连接路径的任何内容。

然后从A，B，C中选出最高的溶液。