[数据结构与算法]576. 出界的路径数

原题链接

题目描述

给你一个大小为 m x n 的网格和一个球。球的起始坐标为 [startRow, startColumn] 。你可以将球移到在四个方向上相邻的单元格内（可以穿过网格边界到达网格之外）。你 最多 可以移动 maxMove 次球。
给你五个整数 m、n、maxMove、startRow 以及 startColumn ，找出并返回可以将球移出边界的路径数量。因为答案可能非常大，返回对 109 + 7 取余 后的结果。
示例 1：

输入：m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0
输出：6
提示：
1 <= m, n <= 50
0 <= maxMove <= 50
0 <= startRow < m
0 <= startColumn < n

解题：

方法1 动态规划

class Solution(object):
    def findPaths(self, m, n, maxMove, startRow, startColumn):
    	# 四个方向
        dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
        # dp[i][j][k]表示移动i步能够到达（i，j）的路径数
        dp = [[[0 for _ in range(n)] for _ in range(m)] for _ in range(maxMove + 1)]
        # 动态规划边界情况
        dp[0][startRow][startColumn] = 1
        ans = 0
        MOD = 1e9 + 7
        for i in range(maxMove):
            for j in range(m):
                for k in range(n):
                    for dir in dirs:
                        newR, newC = j + dir[0], k + dir[1]
                        if newR >= m or newR <= -1 or newC >= n or newC <= -1:
                            ans += dp[i][j][k]
                            ans %= MOD
                        else:
                            dp[i + 1][newR][newC] += dp[i][j][k]
                            dp[i + 1][newR][newC] %= MOD
        return int(ans)

方法2 dfs+记忆化搜索

(这种方法用时最少)

class Solution(object):
    def findPaths(self, m, n, maxMove, startRow, startColumn):
        MOD = 1e9 + 7
        dp = [[[-1 for _ in range(n)] for _ in range(m)] for _ in range(maxMove + 1)]
        def dfs(x, y, k):
        	# 到达边界的情况
            if x < 0 or x >= m or y < 0 or y >= n:
                return 1
            # 没有到达边界但是剩余步数已经不够的情况
            if k == 0:
                return 0
            # 如果之前计算过dp[k][x][y]的值，就直接返回，从而实现记忆化搜索
            if dp[k][x][y] != -1:
                return dp[k][x][y]
            dp[k][x][y] = (dfs(x - 1, y, k - 1) + dfs(x, y - 1, k - 1) + dfs(x + 1, y, k - 1) + dfs(x, y + 1, k - 1)) % MOD
            return dp[k][x][y]
        return int(dfs(startRow, startColumn, maxMove))

队列实现BFS

class Solution(object):
    def findPaths(self, m, n, maxMove, startRow, startColumn):
        q = [(startRow, startColumn)]
        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        dp = [[0 for _ in range(n)] for _ in range(m)]
        dp[startRow][startColumn] = 1
        ans = 0
        MOD = 1e9 + 7
        for _ in range(maxMove): #遍历每种步数
            length = len(q)
            for _ in range(length): #遍历相同步数能够到达的点的情况
                (tmpR, tmpC) = q.pop(0)
                for dir in dirs:
                    newR, newC = tmpR + dir[0], tmpC + dir[1]
                    if newC == -1 or newC == n or newR == -1 or newR == m:
                        ans = (ans + dp[tmpR][tmpC]) % MOD
                    else:
                        if dp[newR][newC] == 0: 
                            q.append((newR, newC))
                        dp[newR][newC] = (dp[newR][newC] + dp[tmpR][tmpC]) % MOD
                dp[tmpR][tmpC] = 0
        return int(ans)