2684. Maximum Number of Moves in a Grid 給一個n*m的二維矩陣裡面都是正整數 從第一行任一個元素開始 滿足下列條件(row,col)可以往(row-1,col+1)、(row,col+1)、(row-1,col+1)移動 你要目標cell的值比現在cell的值還大 請問最多可以做幾次移動? 思路: 就照著題目做 用兩個長度為n的dp矩陣 dp1紀錄matrix[i][j]有沒有路徑可以抵達 dp2紀錄matrix[i][j+1]有沒有路徑可以抵達 從第一行開始一直到第m-1行 如果dp1[i] == j表示matrix[i][j]有路徑可以抵達 接著去檢查三個方向的值有沒有比matrix[i][j]大 有的話對應方向的dp2=dp[i]+1 然後把dp1=dp2並建立一個新的dp2，繼續下一輪 最後把dp1最大的值回傳就好 golang code : func maxMoves(grid [][]int) int { n, m := len(grid), len(grid[0]) tmp1 := make([][]int, 1) tmp1[0] = make([]int, m) tmp2 := make([][]int, 1) tmp2[0] = make([]int, m) grid = append(tmp1, grid...) grid = append(grid, tmp2...) ans := 0 dp1 := make([]int, n+2) dp2 := make([]int, n+2) for j := 0; j < m-1; j++ { for i := 1; i <= n; i++ { if dp1[i] == j { if grid[i][j] < grid[i-1][j+1] { dp2[i-1] = j + 1 ans = max(dp2[i-1], ans) } if grid[i][j] < grid[i][j+1] { dp2[i] = j + 1 ans = max(dp2[i], ans) } if grid[i][j] < grid[i+1][j+1] { dp2[i+1] = j + 1 ans = max(dp2[i+1], ans) } } } dp1 = dp2 dp2 = make([]int, n+2) } return ans } --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.212.104 (臺灣) ※ 文章網址: https://webptt.com/m.aspx?n=bbs/Marginalman/M.1730210871.A.FE8.html