[Swift]LeetCode576.出界的路径数|OutofBoundaryPaths

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

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

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

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

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

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

There is an m by n grid with a ball. Given the start coordinate (i,j) of the ball, you can move the ball to adjacent cell or cross the grid boundary in four directions (up, down, left, right). However, you can at most move Ntimes. Find out the number of paths to move the ball out of grid boundary. The answer may be very large, return it after mod 109 + 7.

Example 1:

Input: m = 2, n = 2, N = 2, i = 0, j = 0
Output: 6
Explanation:

Example 2:

Input: m = 1, n = 3, N = 3, i = 0, j = 1
Output: 12
Explanation:

Note:

Once you move the ball out of boundary, you cannot move it back.
The length and height of the grid is in range [1,50].
N is in range [0,50].

给定一个 m × n 的网格和一个球。球的起始坐标为 (i,j) ，你可以将球移到相邻的单元格内，或者往上、下、左、右四个方向上移动使球穿过网格边界。但是，你最多可以移动 N 次。找出可以将球移出边界的路径数量。答案可能非常大，返回结果 mod 109 + 7 的值。

示例 1：

输入: m = 2, n = 2, N = 2, i = 0, j = 0
输出: 6
解释:

示例 2：

输入: m = 1, n = 3, N = 3, i = 0, j = 1
输出: 12
解释:

说明:

球一旦出界，就不能再被移动回网格内。
网格的长度和高度在 [1,50] 的范围内。
N 在 [0,50] 的范围内。

44ms

 1 class Solution {
 2     func findPaths(_ m: Int, _ n: Int, _ N: Int, _ i: Int, _ j: Int) -> Int {
 3         var dp = [[[Int]]](repeating: [[Int]](repeating: [Int](repeating: -1, count: N+1), count: n), count: m)
 4         return findPaths(m, n, N, i, j, &dp)
 5     }
 6     
 7     func findPaths(_ m: Int, _ n: Int, _ N: Int, _ i: Int, _ j: Int, _ dp: inout [[[Int]]]) -> Int {
 8         // print("\(i), \(j), \(N)")
 9         let minMoves = min(min(i+1, m-i), min(j+1, n-j))
10         if minMoves > N { return 0 }
11         if dp[i][j][N] > -1 { return dp[i][j][N] }
12         if dp[m-i-1][j][N] > -1 { return dp[m-i-1][j][N] }
13         if dp[i][n-j-1][N] > -1 { return dp[i][n-j-1][N] }
14         if dp[m-i-1][n-j-1][N] > -1 { return dp[m-i-1][n-j-1][N] }
15         var res = 0
16         for (d_i, d_j) in [(-1, 0), (1, 0), (0, -1), (0, 1)] {
17             let next_i = i + d_i
18             let next_j = j + d_j
19             if next_i < 0 || next_i >= m || next_j < 0 || next_j >= n {
20                 res += 1
21             } else {
22                 res += findPaths(m, n, N-1, next_i, next_j, &dp)
23                 res = res % 1000000007
24             }
25         }
26         
27         dp[i][j][N] = res 
28         return res
29     }
30 }

104ms

 1 class Solution {    
 2     private let dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]
 3     private let mod = 1000000000 + 7
 4     
 5     func findPaths(_ m: Int, _ n: Int, _ N: Int, _ i: Int, _ j: Int) -> Int {
 6         var memo: [[[Int]]] = Array(repeating: Array(repeating: Array(repeating: -1, count: N + 1), count: n), count: m)
 7         return dfs(m, n, N, i, j, &memo)
 8     }
 9     
10     private func dfs(_ m: Int, _ n: Int, _ N: Int, _ i: Int, _ j: Int, _ memo: inout [[[Int]]]) -> Int {
11         if i < 0 || i >= m || j < 0 || j >= n {
12             return 1
13         }
14         if N == 0 { return 0 }
15         if memo[i][j][N] != -1 { return memo[i][j][N] }
16         memo[i][j][N] = 0
17         for dir in dirs {
18             let x = i + dir[0]
19             let y = j + dir[1]
20             memo[i][j][N] = (memo[i][j][N] + dfs(m, n, N - 1, x, y, &memo) % mod) % mod
21         }
22         return memo[i][j][N]
23     }
24 }

180ms

 1 class Solution {
 2     func findPaths(_ m: Int, _ n: Int, _ N: Int, _ i: Int, _ j: Int) -> Int {
 3         let M = 1000000000 + 7
 4         let memoZero = Array(repeating: Array(repeating: 0, count: n), count: m)
 5         var memo = memoZero
 6         memo[i][j] = 1
 7         var count = 0
 8         for _ in 0..<N {
 9             var temp = memoZero
10             for x in 0..<m {
11                 for y in 0..<n {
12                     let curr = memo[x][y]
13                     if x == m - 1 { count += curr }
14                     if y == n - 1 { count += curr }
15                     if x == 0 { count += curr }
16                     if y == 0 { count += curr }
17                     count %= M
18                     temp[x][y] += x > 0 ? memo[x - 1][y]: 0
19                     temp[x][y] += x < m - 1 ? memo[x + 1][y]: 0
20                     temp[x][y] += y > 0 ? memo[x][y - 1]: 0
21                     temp[x][y] += y < n - 1 ? memo[x][y + 1]: 0
22                     temp[x][y] %= M
23                 }
24             }
25             memo = temp
26         }
27         return count
28     }
29 }

Runtime: 332 ms

Memory Usage: 19 MB

 1 class Solution {
 2     func findPaths(_ m: Int, _ n: Int, _ N: Int, _ i: Int, _ j: Int) -> Int {
 3         var res:Int = 0
 4         var dp:[[Int]] = [[Int]](repeating:[Int](repeating:0,count:n),count:m)
 5         dp[i][j] = 1
 6         var dirs:[[Int]] = [[0,-1],[-1,0],[0,1],[1,0]]
 7         for k in 0..<N
 8         {
 9             var t:[[Int]] = [[Int]](repeating:[Int](repeating:0,count:n),count:m)
10             for r in 0..<m
11             {
12                 for c in 0..<n
13                 {
14                     for dir in dirs
15                     {
16                         var x:Int = r + dir[0]
17                         var y:Int = c + dir[1]
18                         if x < 0 || x >= m || y < 0 || y >= n
19                         {
20                             res = (res + dp[r][c]) % 1000000007
21                         }
22                         else
23                         {
24                             t[x][y] = (t[x][y] + dp[r][c]) % 1000000007
25                         }
26                     }
27                 }
28             }
29             dp = t
30         }
31         return res
32     }
33 }