Leetcode 576.出界的路径数

Posted on |

576.出界的路径数

题目

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

说明:

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

方法

方法1：动态规划 & 三维数组

思路：从坐标[i, j]到其上、下、左、右都需要移动1步，剩余N-1步，那么问题转化为从上、下、左、右移动N-1步，一共有多少种方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution(object):
    def findPaths(self, m, n, N, i, j):
        """
        :type m: int
        :type n: int
        :type N: int
        :type i: int
        :type j: int
        :rtype: int
        """
        dp=[[[0 for _ in range(n)] for _ in range(m)] for _ in range(N+1)]

        for k in range(1,N+1):
            for r in range(m):
                for c in range(n):
                    if r==0:
                        up=1
                    else:
                        up=dp[k-1][r-1][c]

                    if r==m-1:
                        down=1
                    else:
                        down=dp[k-1][r+1][c]

                    if c==0:
                        left=1
                    else:
                        left=dp[k-1][r][c-1]

                    if c==n-1:
                        right=1
                    else:
                        right=dp[k-1][r][c+1]
                    dp[k][r][c]=(up+down+left+right)%1000000007
        return dp[N][i][j]

方法2：动态规划 & 二维数组

At time t, let’s maintain dp[r][c] = the number of paths to (r, c) with t moves, and next[r][c] = the number of paths to (r, c) with t+1 moves.

A ball at (r, c) at time t, can move in one of four directions. If it stays on the board, then it contributes to a path that takes t+1 moves. If it falls off the board, then it contributes to the final answer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution(object):
    def findPaths(self, m, n, N, i, j):
        """
        :type m: int
        :type n: int
        :type N: int
        :type i: int
        :type j: int
        :rtype: int
        """
        M=1000000007
        count=0

        dp=[[0 for _ in range(n)] for _ in range(m)]
        dp[i][j]=1

        for k in range(N):
            next=[[0 for _ in range(n)] for _ in range(m)]
            for r in range(m):
                for c in range(n):
                    for dr,dc in zip((-1,1,0,0),(0,0,-1,1)):
                        if 0<=r+dr<m and 0<=c+dc<n:
                            next[r+dr][c+dc]+=dp[r][c]
                            next[r+dr][c+dc]%=M
                        else:
                            count+=dp[r][c]
                            count%=M
            dp=next
        return count