给定一个 m × n 的网格和一个球。球的起始坐标为 (i,j) ,你可以将球移到相邻的单元格内,或者往上、下、左、右四个方向上移动使球穿过网格边界。但是,你最多可以移动 N 次。找出可以将球移出边界的路径数量。答案可能非常大,返回 结果 mod 109 + 7 的值。
class Solution {
int MOD=(int)1e9+7;
Long memo[][][];
public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
/**
记忆化dfs
*/
memo=new Long[m][n][maxMove+1];
return (int)dfs(m,n,maxMove,startRow,startColumn);
}
public long dfs(int m, int n, int maxMove, int i, int j){
if(i<0||j<0||i>=m||j>=n){
return 1;
}
if(maxMove==0){
return 0;
}
if(memo[i][j][maxMove]!=null){
return memo[i][j][maxMove];
}
long res=0;
res=(res+dfs(m,n,maxMove-1,i-1,j))%MOD;
res=(res+dfs(m,n,maxMove-1,i+1,j))%MOD;
res=(res+dfs(m,n,maxMove-1,i,j-1))%MOD;
res=(res+dfs(m,n,maxMove-1,i,j+1))%MOD;
memo[i][j][maxMove]=res;
return res;
}
}