[Swift]LeetCode741. 摘樱桃 | Cherry Pickup_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

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,then no cherrIEs can be collected.

Example 1:

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

说明:

grID 是一个 N * N 的二维数组，N的取值范围是1 <= N <= 50。每一个 grID[i][j] 都是集合 {-1,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) 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                         continue17                     }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                         continue22                     }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,by: -1) {14                         let y1 = step - x1,y2 = step - x215                         if grID[x1][y1] == -1 || grID[x2][y2] == -1 {16                             pickUpCount[x1][x2] = -117                             continue18                         }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                             continue30                         }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,by:-1)12                 {13                     var j:Int = k - i14                     var q:Int = k - p15                     if j < 0 || j >= n || q < 0 || q >= n || grID[i][j] < 0 || grID[p][q] < 016                     {17                         dp[i][p] = -118                         continue19                     }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 }