51 lines
1.5 KiB
C++
51 lines
1.5 KiB
C++
class Solution {
|
|
private:
|
|
const static unsigned CAP = 1000000007;
|
|
|
|
class dp {
|
|
const int rows;
|
|
const int cols;
|
|
const int maxMove;
|
|
|
|
std::vector<std::vector<std::map<int, unsigned>>> paths;
|
|
|
|
int dfs(int y, int x, int moves) {
|
|
if (y < 0 || y >= rows || x < 0 || x >= cols) {
|
|
// BASE: we got out of the bounds
|
|
return 1;
|
|
}
|
|
|
|
if (moves <= 0) {
|
|
// BASE: all moves were used or there are no moves left
|
|
return 0;
|
|
}
|
|
|
|
if (paths[y][x].count(moves)) {
|
|
// BASE(dynamic): already evaluated
|
|
return paths[y][x][moves];
|
|
}
|
|
|
|
int options = 0;
|
|
for (auto &[dx, dy] : std::vector<std::pair<int, int>>{
|
|
{0, 1}, {1, 0}, {0, -1}, {-1, 0}}) {
|
|
options = (options + dfs(y + dy, x + dx, moves - 1)) % CAP;
|
|
}
|
|
paths[y][x][moves] = options;
|
|
|
|
return options;
|
|
}
|
|
|
|
public:
|
|
dp(int rows, int cols, int maxMove)
|
|
: rows(rows), cols(cols), maxMove(maxMove),
|
|
paths(rows, std::vector<std::map<int, unsigned>>(cols)) {}
|
|
|
|
int get(int row, int col) { return dfs(row, col, maxMove); }
|
|
};
|
|
|
|
public:
|
|
int findPaths(int m, int n, int maxMove, int startRow,
|
|
int startColumn) const {
|
|
return dp(m, n, maxMove).get(startRow, startColumn);
|
|
}
|
|
};
|