impl Solution {
    fn rotate(xx: i64) ->i64 {
        let (mut x, mut y) = (xx, 0);
        while x != 0 {
            let mut k = x % 10;
            if k == 6 {
                k = 9;
            } else if k == 9 {
                k = 6;
            }
            y = y * 10 + k;
            x = x / 10;
        }
        return y;
    }

    fn search(num: i64, n: i32, ans: &mut i32) {
        if num > n as i64 {
            return;
        }
        if num != 0 {
            if num != Self::rotate(num) {
                *ans += 1;
            }
            Self::search(num * 10, n, ans);
        }
        Self::search(num * 10 + 1, n, ans);
        Self::search(num * 10 + 6, n, ans);
        Self::search(num * 10 + 8, n, ans);
        Self::search(num * 10 + 9, n, ans);
    }
    pub fn confusing_number_ii(n: i32) -> i32 {
        let mut ans = 0;
        Self::search(0, n, &mut ans);
        return ans;
    }
}

impl Solution {
    pub fn duplicate_zeros(arr: &mut Vec<i32>) {
        let n = arr.len();
        let mut j = n;
        for i in 0..n {
            if arr[i] == 0 {
                j += 1;
            }
        }
        
        let mut i : i32 = (n  - 1) as i32;
        while i >= 0 {
            j -= 1;
            if j < n {
                arr[j] = arr[i as usize];
            }

            if arr[i as usize] == 0 {
                j-= 1;
                if j < n {
                    arr[j] = 0;
                }
            }
            i -= 1;
        }
    }
}

use std::collections::VecDeque;

impl Solution {
    pub fn shortest_path_binary_matrix(grid: Vec<Vec<i32>>) -> i32 {
        let mut g = grid.clone();
        let n = g.len();
        if n == 0 {
            return -1;
        }
        if g[0][0] == 1 || g[n - 1][n - 1] == 1 {
            return -1;
        }
        if n == 1 {
            return 1;
        }

        let mut q = VecDeque::new();
        q.push_back((0, 0));
        let (dx, dy) : ([i32; 8], [i32; 8]) = ([1, -1, 0, 0, 1, 1, -1, -1],
                                               [0, 0, 1, -1, 1, -1, 1, -1]);
        let mut level = 1;
        while !q.is_empty() {
            let size = q.len();
            level += 1;
            for _i in 0..size {
                let cur = q.front().unwrap().clone(); q.pop_front();
                let (x, y) = (cur.0, cur.1);
                for j in 0..8 {
                    let (xx, yy) = (x + dx[j], y + dy[j]);
                    if xx < 0 || yy < 0 || xx as usize >= n || yy as usize >= n {
                        continue;
                    }
                    let (nx, ny) = (xx as usize, yy as usize);
                    if nx == n - 1 && ny == n - 1 {
                        return level;
                    }
                    if g[nx][ny] == 1 {
                        continue;
                    }
                    g[nx][ny] = 1;
                    q.push_back((nx as i32, ny as i32));
                }
            }
        }
        return -1;
    }
}