algorithm - 一个游客在 2 次步行的阻塞网格中可以访问的最大城市数

Question

忍受问题陈述的长度:

A lazy tourist wants to visit as many interesting locations in a city as possible without going one step further than necessary. Starting from his hotel, located in the north-west corner of city, he intends to take a walk to the south-east corner of the city and then walk back. When walking to the south-east corner, he will only walk east or south, and when walking back to the north-west corner, he will only walk north or west. After studying the city map he realizes that the task is not so simple because some areas are blocked. Therefore he has kindly asked you to write a program to solve his problem.

Given the city map (a 2D grid) where the interesting locations and blocked areas are marked, determine the maximum number of interesting locations he can visit. Locations visited twice are only counted once. W and H (2 ≤ W , H ≤ 100)

我解决这个问题的方法是:

假设第二次遍历是从左上角开始的又一次遍历。

现在Walks可以是这样的:

但我会假设他们是这样的而不影响结果:

现在我们可以在这里尝试应用动态规划了!

DP[i][j][k] - 表示要访问的最大城市数，这样在一次遍历中他在 j，在第二次遍历中他在 k。

A[i][j] - 如果在 (i,j) 处有一个点，则为 +1，如果没有，则为 0，如果被阻塞，则为 -INFinity

现在所有 k < j DP[i][j][k] = INT_MIN (按图)

现在 k==j :

DP[i][j][k] =最大值 {

DP[i][j-1][k] (只要从这个状态向右走，我们就会得到这个循环，看到你不添加 A[i][j] 因为它会被多计)，

DP[i-1][j][k]+A[i][k] (你直接从第 i-1 行向下到 j 和 i ，注意它被添加一次以避免多计数)

}注意:我们不能从右边到第 k 个元素，因为 j 和 k 是相同的元素，因为我假设 j <=k(来自图像)

现在 k>j:

DP[i][j][k] =最大值 {

DP[i][j-1][k] (只要从 j-1 开始，我们就会得到这个重复)，

DP[i-1][j][k]+A[i][k]+A[i][j] (只需添加两个单元格的值，来自第 i-1 行)

DP[i][j][k-1]+A[i][k] (直接从 k-1 到 k )

我的复现有什么bug吗!我从早上开始就一直在调试，但我找不到任何东西!

如果有人想看我的代码并且可能会更正它或者可能会提出一些建议(注意:使用 C++ 并且我过度使用了三元运算符!) Ideone

原始问题的链接:Spoj

Answer 1

我认为两次遍历的解决方案没有考虑到您可能会重新访问您去过的地方(并且实际上是两次遍历相同的路线)