推 a9486l: 大師 01/26 21:15
推 SecondRun: 大師 01/26 21:24
推 ILoveErr: 大師 01/26 21:26
推 oin1104: 大師 01/26 21:50
推 JerryChungYC: 大師 01/26 22:52
※ 引述《Rushia (みけねこ的鼻屎)》之銘言：
: 576. Out of Boundary Paths
: 給你一些數字 m = 列數, n = 行數, maxMove = 移動步數, startRow 和 startColumn為
: 矩陣的出發座標，求出移動 1~maxMove 步後共有幾種結果會走出矩陣外外，因為數字很大
: 要取MOD。
: 1.模擬從起始座標往四個方向前進，如果出界就把res+1 否則繼續往四個方向不斷dfs，
: 直到沒步數或出界。
: 2.直接跑會TLE，因為在走的過程中可能會走到已經算過的點，所以可以用memo記憶化搜
: 索，dp[i][j][k] 表示當前位置最多使用 k 步會走出去的路徑數量。
: Java Code:
: --------------------------------------------
: class Solution {
: private int m, n;
: private Integer[][][] cache;
: private int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
: public int findPaths(int m, int n, int maxMove, int startRow, int
: startColumn) {
: this.m = m;
: this.n = n;
: cache = new Integer[m][n][maxMove + 1];
: return dfs(startRow, startColumn, maxMove);
: }
: private int dfs(int y, int x, int step) {
: if (y < 0 || x < 0 || y == m || x == n) {
: return 1;
: }
: if (step == 0) {
: return 0;
: }
: if (cache[y][x][step] != null) {
: return cache[y][x][step];
: }
: int ans = 0;
: for (int[] dir : dirs) {
: ans += dfs(y + dir[0], x + dir[1], step - 1);
: ans %= 1e9+7;
: }
: return cache[y][x][step] = ans;
: }
: }
: --------------------------------------------
Python3 Code:
class Solution:
def findPaths(self, m: int, n: int, maxMove: int, startRow: int,
startColumn: int) -> int:
moves = [(1,0),(0,1),(-1,0),(0,-1)]
@cache
def dfs(step,x,y):
nonlocal moves,m,n
if x < 0 or y < 0 or x == m or y == n:
return 1
if step == 0:
return 0
ans = 0
for a,b in moves:
ans += dfs(step-1,x+a,y+b)
ans %= 10**9+7
return ans
return dfs(maxMove,startRow,startColumn)
思路差不多
然後我又偷吃步 對不起
不過感覺有點懂dp了
下次出dp題就不用偷吃步了
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.43.164.59 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1706274937.A.FE0.html