【LeetCode 576】 Out of Boundary Paths

Source

题目描述

There is an m by n grid with a ball. Given the start coordinate (i,j) of the ball, you can move the ball to adjacent cell or cross the grid boundary in four directions (up, down, left, right). However, you can at most move N times. Find out the number of paths to move the ball out of grid boundary. The answer may be very large, return it after mod 109 + 7.

Example 1:

Input: m = 2, n = 2, N = 2, i = 0, j = 0
Output: 6

Explanation:
在这里插入图片描述

Example 2:

Input: m = 1, n = 3, N = 3, i = 0, j = 1
Output: 12

Explanation:
在这里插入图片描述

Note:

Once you move the ball out of boundary, you cannot move it back.
The length and height of the grid is in range [1,50].
N is in range [0,50].

思路

尝试了BFS、记忆化搜索…都超时,卡在,74和89组上过不去了…
然后,动态规划。
dp[i][j][k]表示从i,j出发走k步到达外面的路径数。,每一步每个位置,由相邻位置的上一步路径数计算得到。

代码

class Solution {
public:
    int findPaths(int m, int n, int N, int i, int j) {
        if (N == 0) return 0;
        
        int stx = i, sty = j;
        vector<vector<vector<int>>> dp(m+1, vector<vector<int>>(n+1, vector<int>(N+1)));
        
        for (int i=0; i<m; ++i) {
            dp[i][0][1] += 1;
            dp[i][n-1][1] += 1;
        }
        for (int j=0; j<n; ++j) {
            dp[0][j][1] += 1;
            dp[m-1][j][1] += 1;
        }
        
        int res = 0;
        
        for (int k=2; k<=N; ++k) {
            for (int i=0; i<m; ++i) {
                for (int j=0; j<n; ++j) {
                    for (int d=0; d<4; ++d) {
                        int x = i + dir[d][0];
                        int y = j + dir[d][1];
                        if (x >= 0 && x < m && y >= 0 && y < n) {
                            dp[i][j][k] += dp[x][y][k-1];
                            dp[i][j][k] %= MOD;
                        }
                    }
                }
            }
        }
        
        for (int k=1; k<=N; ++k) {
            res += dp[stx][sty][k];
            res %= MOD;
        }
        return res;
    }
private:
    vector<vector<vector<int>>> dp;
    int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    int MOD = 1e9+7;
};

还可以小优化一下,不想改了…
这道题写了好久好久…
今天也是暴躁的一天 QAQ

发布了250 篇原创文章 · 获赞 10 · 访问量 1万+