矩阵遍历没有做最优路径

Question

我遇到了以下问题并试图解决：

grid在代表樱桃田的N x N 中，每个单元格都是三个可能的整数之一。

0表示该单元格为空，可以通过；

1表示该单元格内有一颗樱桃，您可以拾取并穿过它；

-1表示该单元格中有一根刺挡住了你的路。

您的任务是按照以下规则收集尽可能多的樱桃：

从位置 (0, 0) 开始，通过向右或向下移动穿过有效路径单元格（值 > 0 或 1 的单元格）到达 (N-1, N-1)；

到达(N-1, N-1)后，通过向左或向上移动经过有效路径单元格返回到(0, 0)；

当经过一个包含樱桃的路径单元格时，你拿起它，该单元格变成一个空单元格（0）；

如果 (0, 0) 和 (N-1, N-1) 之间没有有效路径，则无法收集到樱桃。

Example 1:

Input: grid =

[[0, 1, -1],

 [1, 0, -1],

 [1, 1,  1]]

Output: 5

Explanation: 

The player started at (0, 0) and went down, down, right right to reach (2, 2).

4 cherries were picked up during this single trip, and the matrix becomes [[0,1,-1],[0,0,-1],[0,0,0]].

Then, the player went left, up, up, left to return home, picking up one more cherry.

The total number of cherries picked up is 5, and this is the maximum possible.

笔记：

grid是一个二维N数组N，其中1 <= N <= 50.

每个grid[i][j]都是集合中的一个整数{-1, 0, 1}。

保证grid[0][0]和grid[N-1][N-1]不为-1。

所以我需要编写一个函数cherryPickup，它接受一个网格并返回最大分数。

我的第一个次优尝试（用 Go 编写）如下，据说它会尝试遍历每条可能的路径，在往返路径完成后将分数存储在切片中，然后返回切片中存在的最大分数：

func cherryPickup(grid [][]int) int {

    values := []int{}

    pVals := &values

    finalPoints := 0

    // Begin top-down path

    traverseAndCollectTopDown(grid, 0, 0, 0, pVals)

    // Find max value in slice

    for i, pathPoints := range values {

        if i == 0 || pathPoints > finalPoints {

            finalPoints = pathPoints

        }

    }

    return finalPoints

}

func isTraversable(grid [][]int, x, y int) bool {

    return (grid[x][y] != -1)

}

func isOnBounds(grid [][]int, x, y int) bool {

    return (x < len(grid) && y < len(grid[0]) && x >= 0 && y >= 0)

}

目前它通过了一系列测试，但这个失败了，我不知道为什么。

输入：[[1,1,1,1,0,0,0],[0,0,0,1,0,0,0],[0,0,0,1,0,0,1],[1,0,0,1,0,0,0],[0,0,0,1,0,0,0],[0,0,0,1,0,0,0],[0,0,0,1,1,1,1]]

输出：10

预计：15

我知道这个网格必须得分 15 分，但是，为什么我的代码无法走上获胜之路，只得分 10 分？另外，您是否推荐任何终端实用程序、程序或策略来帮助更好地可视化每次运行时发生的情况？

Answer 1

您用于traverseAndCollectTopDown/ 的参数traverseAndCollectBottomUp是grid [][]int. 您正在修改它，然后将其直接传递到其他函数（递归地）。在 go 中，切片是通过引用有效传递的，这意味着当您的一个例程编辑该切片时，这也会影响所有其他例程所持有的切片（因此，一旦一条路径找到“1”，它就会被删除，另一条路径也会继续运行）通过同一个单元格会发现那里有一个“0”）。要解决此问题，请在进行递归调用之前获取网格的副本，例如在修改网格之前grid = copyGrid(grid)调用traverseAndCollectTopDown/ traverseAndCollectBottomUp。func copyGrid(in [][]int) [][]int {&nbsp; &nbsp; duplicate := make([][]int, len(in))&nbsp; &nbsp; for i := range in {&nbsp; &nbsp; &nbsp; &nbsp; duplicate[i] = make([]int, len(in[i]))&nbsp; &nbsp; &nbsp; &nbsp; copy(duplicate[i], in[i])&nbsp; &nbsp; }&nbsp; &nbsp; return duplicate&nbsp;}