Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 576. Out of Boundary Paths

---

題目：


解答：

class Solution {
public:
    int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        constexpr int MOD = 1e9 + 7;
        int dp[51][51][51] = { 0 };

        memset(dp, -1, sizeof(dp));

        auto dfs = [&](this auto&& dfs, int r, int c, int cnt) -> int {
            if (r < 0 || r >= m || c < 0 || c >= n) {
                return 1;
            }

            if (cnt == 0) {
                return 0;
            }

            if (dp[r][c][cnt] != -1) {
                return dp[r][c][cnt];
            }

            long long ans = 0;

            ans += dfs(r + 1, c + 0, cnt - 1);
            ans += dfs(r - 1, c + 0, cnt - 1);
            ans += dfs(r + 0, c + 1, cnt - 1);
            ans += dfs(r + 0, c - 1, cnt - 1);

            ans %= MOD;
            dp[r][c][cnt] = ans;

            return ans;
        };

        return dfs(startRow, startColumn, maxMove);
    }
};