1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class Solution {
public:
static constexpr int MOD = 1'000'000'007;
int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
vector<vector<int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int outCounts = 0;
vector<vector<vector<int>>> dp(2, vector<vector<int>>(m, vector<int>(n, 0)));
dp[0][startRow][startColumn] = 1;
int curcol = 0;
for(int i = 0; i < maxMove; i++){
for(int j = 0; j < m; j++){
for(int k = 0; k < n; k++){
int cur = dp[curcol][j][k];
if(!cur)
continue;
for(int z = 0; z < 4; z++){
int x = j + directions[z][0], y = k + directions[z][1];
if(x < 0 || x >= m || y < 0 || y >= n){
outCounts = (outCounts + cur) % MOD;
}else{
dp[curcol^1][x][y] = (dp[curcol^1][x][y] + cur) %MOD;
}
}
dp[curcol][j][k] = 0;
}
}
curcol^=1;
}
return outCounts;
}
};
|
