矩阵遍历需要优化路径

目前golang学习网上已经有很多关于Golang的文章了，自己在初次阅读这些文章中，也见识到了很多学习思路；那么本文《矩阵遍历需要优化路径》，也希望能帮助到大家，如果阅读完后真的对你学习Golang有帮助，欢迎动动手指，评论留言并分享~

我遇到了以下问题，正在尝试解决：

在代表樱桃田的 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) 之间没有有效路径，则无法收集到樱桃。 示例1： 输入：网格= [[0, 1, -1], [1, 0, -1], [1,1,1]] 输出：5 解释： 玩家从 (0, 0) 开始，向下、向下、向右到达 (2, 2)。 单程采摘了 4 个樱桃，矩阵变为 [[0,1,-1],[0,0,-1],[0,0,0]]。 然后，玩家向左、向上、向上、向左回家，又摘了一颗樱桃。 总共能摘到 5 颗樱桃，这是最多能摘到的樱桃。 笔记： grid 是一个 n × n 2d 数组，其中 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)
}

func traverseAndCollectTopDown(grid [][]int, x, y, points int, vals *[]int) {

    // Collect point before continuing
    if grid[x][y] == 1 {
        grid[x][y] = 0
        points++
    }

    // If reached bottom, begin bottom-up path
    if (x == len(grid)-1) && (y == len(grid[0])-1) {
        traverseAndCollectBottomUp(grid, x, y, points, vals)
        return
    }

    // Go Down
    if isOnBounds(grid, x+1, y) && isTraversable(grid, x+1, y) {
        traverseAndCollectTopDown(grid, x+1, y, points, vals)
    }
    // Go Right
    if isOnBounds(grid, x, y+1) && isTraversable(grid, x, y+1) {
        traverseAndCollectTopDown(grid, x, y+1, points, vals)
    }

}

func traverseAndCollectBottomUp(grid [][]int, x, y, points int, vals *[]int) {

    if grid[x][y] == 1 {
        grid[x][y] = 0
        points++
    }

    if x == 0 && y == 0 {
        *vals = append(*vals, points)
        return
    }

    // Go Up
    if isOnBounds(grid, x-1, y) && isTraversable(grid, x-1, y) {
        traverseAndCollectBottomUp(grid, x-1, y, points, vals)
    }
    // Go Left
    if isOnBounds(grid, x, y-1) && isTraversable(grid, x, y-1) {
        traverseAndCollectBottomUp(grid, x, y-1, points, vals)
    }
}

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

输入：[[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 分？另外，您是否推荐任何终端实用程序、程序或策略来帮助更好地可视化每次运行时发生的情况？

提前致谢！

解决方案

您用于 traverseandcollecttopdown / traverseandcollectbottomup 的参数是 grid [][]int。您正在修改它，然后将其直接传递到其他函数（递归地）。在 go 中，切片实际上是 passed by reference，这意味着当您的一个例程编辑该切片时，这也会影响所有其他例程所持有的切片（因此，一旦一条路径找到“1”，它就会被删除，而另一条路径则通过相同的单元格会在那里找到“0”）。

要解决此问题，请在进行递归调用之前获取网格的副本，例如在修改网格之前，在 traverseandcollecttopdown / traverseandcollectbottomup 中调用 grid = copygrid(grid) 。

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 
}

本篇关于《矩阵遍历需要优化路径》的介绍就到此结束啦，但是学无止境，想要了解学习更多关于Golang的相关知识，请关注golang学习网公众号！