python3 解法, 执行用时: 100 ms, 内存消耗: 16.3 MB, 提交时间: 2023-10-24 07:52:15
class Solution:
def findPaths1(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
MOD = 10**9 + 7
outCounts = 0
dp = [[[0] * n for _ in range(m)] for _ in range(maxMove + 1)]
dp[0][startRow][startColumn] = 1
for i in range(maxMove):
for j in range(m):
for k in range(n):
if dp[i][j][k] > 0:
for j1, k1 in [(j - 1, k), (j + 1, k), (j, k - 1), (j, k + 1)]:
if 0 <= j1 < m and 0 <= k1 < n:
dp[i + 1][j1][k1] = (dp[i + 1][j1][k1] + dp[i][j][k]) % MOD
else:
outCounts = (outCounts + dp[i][j][k]) % MOD
return outCounts
def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
MOD = 10**9 + 7
outCounts = 0
dp = [[0] * n for _ in range(m)]
dp[startRow][startColumn] = 1
for i in range(maxMove):
dpNew = [[0] * n for _ in range(m)]
for j in range(m):
for k in range(n):
if dp[j][k] > 0:
for j1, k1 in [(j - 1, k), (j + 1, k), (j, k - 1), (j, k + 1)]:
if 0 <= j1 < m and 0 <= k1 < n:
dpNew[j1][k1] = (dpNew[j1][k1] + dp[j][k]) % MOD
else:
outCounts = (outCounts + dp[j][k]) % MOD
dp = dpNew
return outCounts
java 解法, 执行用时: 4 ms, 内存消耗: 39.8 MB, 提交时间: 2023-10-24 07:51:45
class Solution {
public int findPaths1(int m, int n, int maxMove, int startRow, int startColumn) {
final int MOD = 1000000007;
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int outCounts = 0;
int[][][] dp = new int[maxMove + 1][m][n];
dp[0][startRow][startColumn] = 1;
for (int i = 0; i < maxMove; i++) {
for (int j = 0; j < m; j++) {
for (int k = 0; k < n; k++) {
int count = dp[i][j][k];
if (count > 0) {
for (int[] direction : directions) {
int j1 = j + direction[0], k1 = k + direction[1];
if (j1 >= 0 && j1 < m && k1 >= 0 && k1 < n) {
dp[i + 1][j1][k1] = (dp[i + 1][j1][k1] + count) % MOD;
} else {
outCounts = (outCounts + count) % MOD;
}
}
}
}
}
}
return outCounts;
}
public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
final int MOD = 1000000007;
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int outCounts = 0;
int[][] dp = new int[m][n];
dp[startRow][startColumn] = 1;
for (int i = 0; i < maxMove; i++) {
int[][] dpNew = new int[m][n];
for (int j = 0; j < m; j++) {
for (int k = 0; k < n; k++) {
int count = dp[j][k];
if (count > 0) {
for (int[] direction : directions) {
int j1 = j + direction[0], k1 = k + direction[1];
if (j1 >= 0 && j1 < m && k1 >= 0 && k1 < n) {
dpNew[j1][k1] = (dpNew[j1][k1] + count) % MOD;
} else {
outCounts = (outCounts + count) % MOD;
}
}
}
}
}
dp = dpNew;
}
return outCounts;
}
}
