我遇到了以下問題并試圖解決:grid在代表櫻桃田的N x N 中,每個單元格都是三個可能的整數(shù)之一。0表示該單元格為空,可以通過;1表示該單元格內有一顆櫻桃,您可以拾取并穿過它;-1表示該單元格中有一根刺擋住了你的路。您的任務是按照以下規(guī)則收集盡可能多的櫻桃:從位置 (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數(shù)組N,其中1 <= N <= 50.每個grid[i][j]都是集合中的一個整數(shù){-1, 0, 1}。保證grid[0][0]和grid[N-1][N-1]不為-1。所以我需要編寫一個函數(shù)cherryPickup,它接受一個網(wǎng)格并返回最大分數(shù)。我的第一個次優(yōu)嘗試(用 Go 編寫)如下,據(jù)說它會嘗試遍歷每條可能的路徑,在往返路徑完成后將分數(shù)存儲在切片中,然后返回切片中存在的最大分數(shù):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我知道這個網(wǎng)格必須得分 15 分,但是,為什么我的代碼無法走上獲勝之路,只得分 10 分?另外,您是否推薦任何終端實用程序、程序或策略來幫助更好地可視化每次運行時發(fā)生的情況?
1 回答

縹緲止盈
TA貢獻2041條經驗 獲得超4個贊
您用于traverseAndCollectTopDown/ 的參數(shù)traverseAndCollectBottomUp是grid [][]int. 您正在修改它,然后將其直接傳遞到其他函數(shù)(遞歸地)。在 go 中,切片是通過引用有效傳遞的,這意味著當您的一個例程編輯該切片時,這也會影響所有其他例程所持有的切片(因此,一旦一條路徑找到“1”,它就會被刪除,另一條路徑也會繼續(xù)運行)通過同一個單元格會發(fā)現(xiàn)那里有一個“0”)。
要解決此問題,請在進行遞歸調用之前獲取網(wǎng)格的副本,例如在修改網(wǎng)格之前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
}
- 1 回答
- 0 關注
- 136 瀏覽
添加回答
舉報
0/150
提交
取消