LeetCode 688. Knight Probability in Chessboard

Problem Statement

DP, be careful about pow overflow.

impl Solution {
    pub fn knight_probability(n: i32, k: i32, r: i32, c: i32) -> f64 {
        if k == 0 {
            return 1 as f64;
        }

        let (dx, dy) : ([i32; 8], [i32; 8]) = (
            [-1, -2, -2, -1, 1, 2, 2, 1],
            [-2, -1, 1, 2, 2, 1, -1, -2]);
        let mut dp = vec![vec![1 as f64; n as usize]; n as usize];
        for _m in 0..k {
            let mut tmp = vec![vec![0 as f64; n as usize]; n as usize];
            for i in 0..n {
                for j in 0..n {
                    for k in 0..8 {
                        let (xx, yy) = (i + dx[k], j + dy[k]);
                        if xx < 0 || yy < 0 || xx >= n || yy >= n {
                            continue;
                        }
                        tmp[i as usize][j as usize] += dp[xx as usize][yy as usize];
                    }
                }
            }
            dp.swap_with_slice(&mut tmp[0..]);
        }

        return dp[r as usize][c as usize] / 8_f64.powf(k as f64);
    }
}