本文主要是介绍出界的路径数(记忆化bfs),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
记忆化dfs 已遍历过的点他的方案数已知晓 所以无需重新遍历
class Solution {int MOD = (int)1e9 + 7;int[][][] dp;int m1,n1,maxstep=0;public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {m1=m;n1=n;maxstep=maxMove;dp=new int[m][n][maxMove+1];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {Arrays.fill(dp[i][j], -1);}}return dfs(0, startRow, startColumn);}public int dfs(int step, int r, int c) {if (r >= m1 || c >= n1 || r < 0 || c < 0) {//越界+1return 1;}if (step >= maxstep) {//步数超限,但没越界应该返回0return 0;}if (dp[r][c][step] != -1) {//表示这个点已经遍历过了,所以无需再次遍历return dp[r][c][step];}dp[r][c][step]= 0;//未遍历的点当前方案数应该初始化置0dp[r][c][step]=(dp[r][c][step]+dfs(step + 1, r + 1, c) % MOD)%MOD;dp[r][c][step]=(dp[r][c][step]+dfs(step + 1, r - 1, c) % MOD)%MOD;dp[r][c][step]=(dp[r][c][step]+dfs(step + 1, r, c + 1) % MOD)%MOD;dp[r][c][step]=(dp[r][c][step]+dfs(step + 1, r, c - 1) % MOD)%MOD;return dp[r][c][step];}
}
这篇关于出界的路径数(记忆化bfs)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!