• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

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

原作者: [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:

  1. Once you move the ball out of boundary, you cannot move it back.
  2. The length and height of the grid is in range [1,50].
  3. 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. 球一旦出界,就不能再被移动回网格内。
  2. 网格的长度和高度在 [1,50] 的范围内。
  3. 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 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap