[Swift]LeetCode741.摘樱桃|CherryPickup

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10522356.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

In a N x N grid representing a field of cherries, each cell is one of three possible integers.

0 means the cell is empty, so you can pass through;
1 means the cell contains a cherry, that you can pick up and pass through;
-1 means the cell contains a thorn that blocks your way.

Your task is to collect maximum number of cherries possible by following the rules below:

Starting at the position (0, 0) and reaching (N-1, N-1) by moving right or down through valid path cells (cells with value 0 or 1);
After reaching (N-1, N-1), returning to (0, 0) by moving left or up through valid path cells;
When passing through a path cell containing a cherry, you pick it up and the cell becomes an empty cell (0);
If there is no valid path between (0, 0) and (N-1, N-1), then no cherries can be collected.

Example 1:

Input: grid =
[[0, 1, -1],
 [1, 0, -1],
 [1, 1,  1]]
Output: 5
Explanation: 
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.

Note:

grid is an N by N 2D array, with 1 <= N <= 50.
Each grid[i][j] is an integer in the set {-1, 0, 1}.
It is guaranteed that grid[0][0] and grid[N-1][N-1] are not -1.

一个N x N的网格(grid) 代表了一块樱桃地，每个格子由以下三种数字的一种来表示：

0 表示这个格子是空的，所以你可以穿过它。
1 表示这个格子里装着一个樱桃，你可以摘到樱桃然后穿过它。
-1 表示这个格子里有荆棘，挡着你的路。

你的任务是在遵守下列规则的情况下，尽可能的摘到最多樱桃：

从位置 (0, 0) 出发，最后到达 (N-1, N-1) ，只能向下或向右走，并且只能穿越有效的格子（即只可以穿过值为0或者1的格子）；
当到达 (N-1, N-1) 后，你要继续走，直到返回到 (0, 0) ，只能向上或向左走，并且只能穿越有效的格子；
当你经过一个格子且这个格子包含一个樱桃时，你将摘到樱桃并且这个格子会变成空的（值变为0）；
如果在 (0, 0) 和 (N-1, N-1) 之间不存在一条可经过的路径，则没有任何一个樱桃能被摘到。

示例 1:

输入: grid =
[[0, 1, -1],
 [1, 0, -1],
 [1, 1,  1]]
输出: 5
解释： 
玩家从（0,0）点出发，经过了向下走，向下走，向右走，向右走，到达了点(2, 2)。
在这趟单程中，总共摘到了4颗樱桃，矩阵变成了[[0,1,-1],[0,0,-1],[0,0,0]]。
接着，这名玩家向左走，向上走，向上走，向左走，返回了起始点，又摘到了1颗樱桃。
在旅程中，总共摘到了5颗樱桃，这是可以摘到的最大值了。

说明:

grid 是一个 N * N 的二维数组，N的取值范围是1 <= N <= 50。
每一个 grid[i][j] 都是集合 {-1, 0, 1}其中的一个数。
可以保证起点 grid[0][0] 和终点 grid[N-1][N-1] 的值都不会是 -1。

384ms

 1 class Solution {
 2     func cherryPickup(_ grid: [[Int]]) -> Int {
 3         let n = grid.count
 4         var dp = Array(repeating: Array(repeating: Array(repeating: -1, count: n+1), count: n+1), count: n+1)
 5         
 6         dp[1][1][1] = grid[0][0]
 7         for x1 in 1...n {
 8             for y1 in 1...n {
 9                 for x2 in 1...n {
10                     let y2 = x1 + y1 - x2;
11                     if dp[x1][y1][x2] > 0 ||
12                         y2 < 1 || 
13                         y2 > n || 
14                         grid[x1 - 1][y1 - 1] == -1 || 
15                         grid[x2 - 1][y2 - 1] == -1 {
16                         continue
17                     }
18                     let cur = max(max(dp[x1 - 1][y1][x2], dp[x1 - 1][y1][x2 - 1]), 
19                                   max(dp[x1][y1 - 1][x2], dp[x1][y1 - 1][x2 - 1]))
20                     if cur < 0 {
21                         continue
22                     }
23                     dp[x1][y1][x2] = cur + grid[x1 - 1][y1 - 1]
24                     if x1 != x2 {
25                         dp[x1][y1][x2] += grid[x2 - 1][y2 - 1]
26                     }
27                 }
28             }
29         }
30         return dp[n][n][n] < 0 ? 0 : dp[n][n][n]
31     }
32 }

740ms

 1 class Solution {
 2     func cherryPickup(_ grid: [[Int]]) -> Int {
 3         let length = grid.count
 4         guard length != 0 && length == grid.first!.count && length >= 1 && length <= 50 && grid[0][0] != -1 && grid[length - 1][length - 1] != -1 else {
 5             return 0
 6         }
 7         var pickUpCount = Array(repeating: Array(repeating: -1, count: length), count: length)
 8         pickUpCount[0][0] = grid[0][0]
 9         if length > 1 {
10             for step in 1 ... (length - 1) * 2 {
11                 let xMax = min(length - 1, step), xMin = max(0, step - (length - 1))
12                 for x1 in stride(from: xMax, through: xMin, by: -1) {
13                     for x2 in stride(from: xMax, through: xMin, by: -1) {
14                         let y1 = step - x1, y2 = step - x2
15                         if grid[x1][y1] == -1 || grid[x2][y2] == -1 {
16                             pickUpCount[x1][x2] = -1
17                             continue
18                         }
19                         if y1 > 0 && x2 > 0 {
20                             pickUpCount[x1][x2] = max(pickUpCount[x1][x2], pickUpCount[x1][x2 - 1])
21                         }
22                         if x1 > 0 && y2 > 0 {
23                             pickUpCount[x1][x2] = max(pickUpCount[x1][x2], pickUpCount[x1 - 1][x2])
24                         }
25                         if x1 > 0 && x2 > 0 {
26                             pickUpCount[x1][x2] = max(pickUpCount[x1][x2], pickUpCount[x1 - 1][x2 - 1])
27                         }
28                         if pickUpCount[x1][x2] == -1 {
29                             continue
30                         }
31                         if x1 == x2 {
32                             pickUpCount[x1][x2] += grid[x1][y1]
33                         } else {
34                             pickUpCount[x1][x2] += grid[x1][y1] + grid[x2][y2]
35                         }
36                     }
37                 }
38             }
39         }
40         return max(pickUpCount[length - 1][length - 1], 0)
41     }
42 }

Runtime: 876 ms

Memory Usage: 19 MB

 1 class Solution {
 2     func cherryPickup(_ grid: [[Int]]) -> Int {
 3         var n:Int = grid.count
 4         var mx:Int = 2 * n - 1
 5         var dp:[[Int]] = [[Int]](repeating:[Int](repeating:-1,count:n),count:n)
 6         dp[0][0] = grid[0][0]
 7         for k in 1..<mx
 8         {
 9             for i in stride(from:n - 1,through:0,by:-1)
10             {
11                 for p in stride(from:n - 1,through:0,by:-1)
12                 {
13                     var j:Int = k - i
14                     var q:Int = k - p
15                     if j < 0 || j >= n || q < 0 || q >= n || grid[i][j] < 0 || grid[p][q] < 0
16                     {
17                         dp[i][p] = -1
18                         continue
19                     }
20                     if i > 0 {dp[i][p] = max(dp[i][p], dp[i - 1][p])}
21                     if p > 0 {dp[i][p] = max(dp[i][p], dp[i][p - 1])}
22                     if i > 0 && p > 0 {dp[i][p] = max(dp[i][p], dp[i - 1][p - 1])}
23                     if dp[i][p] >= 0 {dp[i][p] += grid[i][j] + (i != p ? grid[p][q] : 0)}
24                 }
25             }
26         }
27         return max(dp[n - 1][n - 1], 0)
28     }
29 }