跳转至

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

示例 2：

输入：m = 1, n = 3, maxMove = 3, startRow = 0, startColumn = 1
输出：12

 

提示：

  • 1 <= m, n <= 50
  • 0 <= maxMove <= 50
  • 0 <= startRow < m
  • 0 <= startColumn < n

解法

方法一：记忆化搜索

定义 dfs(i, j, k) 表示当前位于坐标 $(i, j)$，且剩余移动次数为 $k$ 时，可以出界的路径数。记忆化搜索即可。

时间复杂度 $O(m\times n\times k)$，空间复杂度 $O(m\times n\times k)$。其中 $m$, $n$, $k$ 分别表示网格的行数、列数、最大可移动次数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def findPaths(
        self, m: int, n: int, maxMove: int, startRow: int, startColumn: int
    ) -> int:
        @cache
        def dfs(i, j, k):
            if i < 0 or j < 0 or i >= m or j >= n:
                return 1
            if k <= 0:
                return 0
            res = 0
            for a, b in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
                x, y = i + a, j + b
                res += dfs(x, y, k - 1)
                res %= mod
            return res

        mod = 10**9 + 7
        return dfs(startRow, startColumn, maxMove)

 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
37
38
39
40
class Solution {
    private int m;
    private int n;
    private int[][][] f;
    private static final int[] DIRS = {-1, 0, 1, 0, -1};
    private static final int MOD = (int) 1e9 + 7;

    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        this.m = m;
        this.n = n;
        f = new int[m + 1][n + 1][maxMove + 1];
        for (var a : f) {
            for (var b : a) {
                Arrays.fill(b, -1);
            }
        }
        return dfs(startRow, startColumn, maxMove);
    }

    private int dfs(int i, int j, int k) {
        if (i < 0 || i >= m || j < 0 || j >= n) {
            return 1;
        }
        if (f[i][j][k] != -1) {
            return f[i][j][k];
        }
        if (k == 0) {
            return 0;
        }
        int res = 0;
        for (int t = 0; t < 4; ++t) {
            int x = i + DIRS[t];
            int y = j + DIRS[t + 1];
            res += dfs(x, y, k - 1);
            res %= MOD;
        }
        f[i][j][k] = res;
        return res;
    }
}

 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 {
public:
    int m;
    int n;
    const int mod = 1e9 + 7;
    int f[51][51][51];
    int dirs[5] = {-1, 0, 1, 0, -1};

    int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        memset(f, 0xff, sizeof(f));
        this->m = m;
        this->n = n;
        return dfs(startRow, startColumn, maxMove);
    }

    int dfs(int i, int j, int k) {
        if (i < 0 || i >= m || j < 0 || j >= n) return 1;
        if (f[i][j][k] != -1) return f[i][j][k];
        if (k == 0) return 0;
        int res = 0;
        for (int t = 0; t < 4; ++t) {
            int x = i + dirs[t], y = j + dirs[t + 1];
            res += dfs(x, y, k - 1);
            res %= mod;
        }
        f[i][j][k] = res;
        return res;
    }
};

 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
func findPaths(m int, n int, maxMove int, startRow int, startColumn int) int {
    f := make([][][]int, m+1)
    for i := range f {
        f[i] = make([][]int, n+1)
        for j := range f[i] {
            f[i][j] = make([]int, maxMove+1)
            for k := range f[i][j] {
                f[i][j][k] = -1
            }
        }
    }
    var mod int = 1e9 + 7
    dirs := []int{-1, 0, 1, 0, -1}
    var dfs func(i, j, k int) int
    dfs = func(i, j, k int) int {
        if i < 0 || i >= m || j < 0 || j >= n {
            return 1
        }
        if f[i][j][k] != -1 {
            return f[i][j][k]
        }
        if k == 0 {
            return 0
        }
        res := 0
        for t := 0; t < 4; t++ {
            x, y := i+dirs[t], j+dirs[t+1]
            res += dfs(x, y, k-1)
            res %= mod
        }
        f[i][j][k] = res
        return res
    }
    return dfs(startRow, startColumn, maxMove)
}

方法二

 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
class Solution {
    public int findPaths(int m, int n, int N, int i, int j) {
        final int MOD = (int) (1e9 + 7);
        final int[] dirs = new int[] {-1, 0, 1, 0, -1};
        int[][] f = new int[m][n];
        f[i][j] = 1;
        int res = 0;
        for (int step = 0; step < N; ++step) {
            int[][] temp = new int[m][n];
            for (int x = 0; x < m; ++x) {
                for (int y = 0; y < n; ++y) {
                    for (int k = 0; k < 4; ++k) {
                        int tx = x + dirs[k], ty = y + dirs[k + 1];
                        if (tx >= 0 && tx < m && ty >= 0 && ty < n) {
                            temp[tx][ty] += f[x][y];
                            temp[tx][ty] %= MOD;
                        } else {
                            res += f[x][y];
                            res %= MOD;
                        }
                    }
                }
            }
            f = temp;
        }
        return res;
    }
}

评论