矩阵遍历没有做最优路径

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: 5Explanation: 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 {

    duplicate := make([][]int, len(in))

    for i := range in {

        duplicate[i] = make([]int, len(in[i]))

        copy(duplicate[i], in[i])

    }

    return duplicate 

}