Leetcode 576 Out of Boundary Paths

发表于 |

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



说明:

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

分析：

  1. 这道题乍一看很像一个标准的bfs，因为限定最多只能移动N次，我们只要bfs依次遍历发现出界就+1，当bfs的深度大于N的时候break。当然理论上是没有任何问题的，确实能得出正确答案，但是这里N的取值范围达到了50，我们对任意一个点bfs有四个方向（可以走回头路），那么复杂度达到了4^N，显然会超时。当然我会在文章后面给出bfs的做法，毕竟这是可以处理N比较小的情况的解法，让大家更熟悉bfs的套路。
  2. 我不知道你们有没有这种感觉，一般看到这个mod 1e9+7，这道题8成就是dp了，而且就是那种每个dp值你都得mod一下再去进行运算的那种。我觉得这算一个小技巧吧，看到mod 1e9+7就要想到dp。
  3. 显然，这里dp很好定义，我们定义dp[(i,j,N)]表示从i,j出发，最多走N步情况下满足题意的路径数量，那么我们所求也就是dp[(i,j,N)]。根据我们上面说的bfs的思路，递推式可得：
    dp[(i,j,N)] = dp[(i+1,j,N-1)] + dp[(i-1,j,N-1)] + dp[(i,j+1,N-1)] + dp[(i,j-1,N-1)]

思路：

  1. 处理好边界情况：
    1. 当i,j仍然在网格内时，如果N=0，说明这条路走不出去,dp[(i,j,N)] = 0
    2. 当i,j仍然在网格内时，如果N>0，如递推式
    3. 当i,j在网格外时，说明已经走出去，dp[(i,j,N)] = 1
  2. 这里我为了方便代码书写就用的记忆化的形式，用一个cache来存储已经计算过的结果
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
class Solution(object):
    def findPaths(self, m, n, N, i, j):
        mod = 10**9 + 7
        cache = collections.defaultdict(int)
        def helper(i,j,N):
            # 记忆化思想
            if (i,j,N) in cache:
                return cache[(i,j,N)]
            #i,j在网格内情况
            if 0<=i<m and 0<=j<n:
                if N == 0:
                    cache[(i,j,N)] = 0
                    return cache[(i,j,N)]

                for x,y in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
                    cache[(i,j,N)] += helper(x,y,N-1)
                return cache[(i,j,N)] % mod
            # 网格外情况
            else:
                cache[(i,j,N)] = 1
                return cache[(i,j,N)]
        return helper(i,j,N) % mod

94 / 94 test cases passed.
difficulty: medium
Runtime: 272 ms

下面是bfs代码，在这道题中tle

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def findPaths(m,n,N,i,j):
    mod = 10**9 + 7
    Q = collections.deque([(i,j,0)])
    res = 0
    while Q:
        x,y,step = Q.popleft()
        if step > N: break
        if 0<=x<m and 0<=y<n:
            Q.append((x+1,y,step+1))
            Q.append((x-1,y,step+1))
            Q.append((x,y+1,step+1))
            Q.append((x,y-1,step+1))
        else:
            res += 1
    return res % mod