LeetCode576-出界的路径数

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/out-of-boundary-paths/

中文链接：https://leetcode-cn.com/problems/out-of-boundary-paths/

题目详述

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

示例 1：

1
2
输入: m = 2, n = 2, N = 2, i = 0, j = 0
输出: 6

示例 2：

1
2
输入: m = 1, n = 3, N = 3, i = 0, j = 1
输出: 12

说明:

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

题目详解

记忆化搜索。dp[i][j][k] 表示处于坐标 (i, j) 剩下 k 步时可以将球移出边界的路径数量。

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
public class LeetCode_00576 {

    int[][] dirs = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    final int MOD = (int) (1e9 + 7);

    public int findPaths(int m, int n, int N, int i, int j) {
        int[][][] dp = new int[m][n][N + 1];
        // 初始化为一个不可能的值
        for (int[][] am : dp) {
            for (int[] an : am) {
                Arrays.fill(an, -1);
            }
        }
        return dfs(m, n, N, i, j, dp);
    }

    private int dfs(int m, int n, int k, int i, int j, int[][][] dp) {
        if (i < 0 || i == m || j < 0 || j == n) {
            return 1;
        }
        if (k == 0) {
            return 0;
        }
        if (dp[i][j][k] != -1) {
            return dp[i][j][k];
        }
        int res = 0;
        for (int[] dir : dirs) {
            int x = i + dir[0], y = j + dir[1];
            res += dfs(m, n, k - 1, x, y, dp);
            res %= MOD;
        }
        dp[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
public class LeetCode_00576 {

    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;
    }
}