1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
impl Solution {
pub fn find_paths(m: i32, n: i32, max_move: i32, start_row: i32, start_column: i32) -> i32 {
const MOD: i32 = 1_000_000_007;
use std::collections::HashMap;
fn dp(move: i32, r: i32, c: i32, m: i32, n: i32, memo: &mut HashMap<(i32,i32,i32),i32>) -> i32 {
if r < 0 || r >= m || c < 0 || c >= n { return 1; }
if move == 0 { return 0; }
if let Some(&v) = memo.get(&(move,r,c)) { return v; }
let mut ans = 0;
ans = (ans + dp(move-1, r-1, c, m, n, memo)) % MOD;
ans = (ans + dp(move-1, r+1, c, m, n, memo)) % MOD;
ans = (ans + dp(move-1, r, c-1, m, n, memo)) % MOD;
ans = (ans + dp(move-1, r, c+1, m, n, memo)) % MOD;
memo.insert((move,r,c), ans);
ans
}
let mut memo = HashMap::new();
dp(max_move, start_row, start_column, m, n, &mut memo)
}
}
|