LeetCode 935. Knight Dialer

Problem Statement

Dynamic Programming

impl Solution {
    pub fn knight_dialer(n: i32) -> i32 {
        const MOD : u64 = 1e9 as u64 + 7;
        const dirs: [(i32, i32); 8] = [(-2, -1), (-2, 1), (-1, -2), (-1, 2),
            (1, -2), (1, 2), (2, -1), (2, 1)];
        let mut dp = [[1; 3] ; 4];
        dp[3][0] = 0; dp[3][2] = 0;
        for k in 1..n {
            let mut tmp = [[0; 3] ; 4];
            for i in 0..4 {
                for j in 0..3 {
                    if i == 3 && j != 1 {
                        continue;
                    }
                    for d in 0..8 {
                        let (xx, yy) = (j + dirs[d].0, i + dirs[d].1);
                        if xx < 0 || yy < 0 || xx >= 3 || yy >= 4 {
                            continue;
                        }
                        tmp[i as usize][j as usize] = (tmp[i as usize][j as usize] +
                            dp[yy as usize][xx as usize]) % MOD;
                    }
                }
            }
            dp.swap_with_slice(&mut tmp[0..]);
        }

        let mut ans : i32 = 0;
        for i in 0..4 {
            for j in 0..3 {
                ans = ((ans as u64 + dp[i][j]) % MOD) as i32;
            }
        }
        return ans;
    }
}