Merge pull request halfrost#85 from frankegoesdown/1436-Cherry-Pickup-II

halfrost · web-flow · commit a6ffd5258aea · 2021-01-25T16:49:47.000+08:00
1436 cherry pickup ii
diff --git a/leetcode/1463.Cherry-Pickup-II/1463.Cherry-Pickup-II.go b/leetcode/1463.Cherry-Pickup-II/1463.Cherry-Pickup-II.go
@@ -0,0 +1,45 @@
+package leetcode
+
+func cherryPickup(grid [][]int) int {
+	m, n := len(grid), len(grid[0])
+	old, new := make([]int, n*n), make([]int, n*n)
+	for i := range old {
+		old[i] = -0xffffff
+	}
+	old[n-1] = grid[0][0]+grid[0][n-1]
+
+	// dp
+	for k:=1; k<m; k++ {
+		for s:=0; s<n*n; s++ {
+			new[s] = -0xffffff
+			c1, c2 := s/n, s%n
+			toadd := grid[k][c1]
+			if c1 != c2 {
+				toadd += grid[k][c2]
+			}
+			for _, d1 := range []int{1,0,-1} {
+				for _, d2 := range []int{1,0,-1} {
+					nc1, nc2 := c1+d1, c2+d2
+					if nc1>=0 && nc1<n && nc2>=0 && nc2<n && old[nc1*n+nc2]>=0 {
+						new[s] = max(new[s], old[nc1*n+nc2]+toadd)
+					}
+				}
+			}
+		}
+		old, new = new, old
+	}
+	allmax := 0
+	for _, v := range old {
+		if v>allmax {
+			allmax = v
+		}
+	}
+	return allmax
+}
+
+func max(a, b int) int {
+	if a>b {
+		return a
+	}
+	return b
+}
diff --git a/leetcode/1463.Cherry-Pickup-II/1463.Cherry-Pickup-II_test.go b/leetcode/1463.Cherry-Pickup-II/1463.Cherry-Pickup-II_test.go
@@ -0,0 +1,71 @@
+package leetcode
+
+import (
+	"fmt"
+	"testing"
+)
+
+type question1436 struct {
+	para1436
+	ans1436
+}
+
+type para1436 struct {
+	grid [][]int
+}
+
+type ans1436 struct {
+	ans int
+}
+
+func Test_Problem1436(t *testing.T) {
+
+	qs := []question1436{
+
+		{
+			para1436{[][]int{
+				{3, 1, 1},
+				{2, 5, 1},
+				{1, 5, 5},
+				{2, 1, 1},
+			}},
+			ans1436{24},
+		},
+
+		{
+			para1436{[][]int{
+				{1, 0, 0, 0, 0, 0, 1},
+				{2, 0, 0, 0, 0, 3, 0},
+				{2, 0, 9, 0, 0, 0, 0},
+				{0, 3, 0, 5, 4, 0, 0},
+				{1, 0, 2, 3, 0, 0, 6},
+			}},
+			ans1436{28},
+		},
+		{
+			para1436{[][]int{
+				{1, 0, 0, 3},
+				{0, 0, 0, 3},
+				{0, 0, 3, 3},
+				{9, 0, 3, 3},
+			}},
+			ans1436{22},
+		},
+		{
+			para1436{[][]int{
+				{1, 1},
+				{1, 1},
+			}},
+			ans1436{4},
+		},
+	}
+
+	fmt.Printf("------------------------Leetcode Problem 1436------------------------\n")
+
+	for _, q := range qs {
+		_, p := q.ans1436, q.para1436
+		fmt.Printf("【input】:%v      ", p)
+		fmt.Printf("【output】:%v      \n", cherryPickup(p.grid))
+	}
+	fmt.Printf("\n\n\n")
+}
diff --git a/leetcode/1463.Cherry-Pickup-II/README.md b/leetcode/1463.Cherry-Pickup-II/README.md
@@ -0,0 +1,44 @@
+# [1463. Cherry Pickup II](https://leetcode.com/problems/cherry-pickup-ii/)
+Given a rows x cols matrix grid representing a field of cherries. Each cell in grid represents the number of cherries that you can collect.
+
+You have two robots that can collect cherries for you, Robot #1 is located at the top-left corner (0,0) , and Robot #2 is located at the top-right corner (0, cols-1) of the grid.
+
+Return the maximum number of cherries collection using both robots  by following the rules below:
+
+    From a cell (i,j), robots can move to cell (i+1, j-1) , (i+1, j) or (i+1, j+1).
+    When any robot is passing through a cell, It picks it up all cherries, and the cell becomes an empty cell (0).
+    When both robots stay on the same cell, only one of them takes the cherries.
+    Both robots cannot move outside of the grid at any moment.
+    Both robots should reach the bottom row in the grid.
+
+## Example 1:
+```
+Input: grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
+Output: 24
+Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
+Cherries taken by Robot #1, (3 + 2 + 5 + 2) = 12.
+Cherries taken by Robot #2, (1 + 5 + 5 + 1) = 12.
+Total of cherries: 12 + 12 = 24.
+```
+
+## Example 2:
+```
+Input: grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]
+Output: 28
+Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
+Cherries taken by Robot #1, (1 + 9 + 5 + 2) = 17.
+Cherries taken by Robot #2, (1 + 3 + 4 + 3) = 11.
+Total of cherries: 17 + 11 = 28.
+```
+
+## Example 3:
+```
+Input: grid = [[1,0,0,3],[0,0,0,3],[0,0,3,3],[9,0,3,3]]
+Output: 22
+```
+
+## Example 4:
+```
+Input: grid = [[1,1],[1,1]]
+Output: 4
+```
