use std::collections::VecDeque;

impl Solution {
    fn dfs(grid: &mut Vec<Vec<i32>>, x: i32, y:i32, q: &mut VecDeque<(i32, i32)>) {
        if x < 0 || y < 0 || y >= grid[0].len() as i32 ||
            x >= grid.len() as i32 || grid[x as usize][y as usize] != 1 {
            return;
        }
        grid[x as usize][y as usize] = 2;
        q.push_back((x, y));
        Self::dfs(grid, x - 1, y, q);
        Self::dfs(grid, x, y - 1, q);
        Self::dfs(grid, x + 1, y, q);
        Self::dfs(grid, x, y + 1, q);
    }

    pub fn shortest_bridge(a: Vec<Vec<i32>>) -> i32 {
        let mut q = VecDeque::new();
        let mut find = false;
        let mut grid = a.clone();
        for i in 0..a.len() {
            if find {
                break;
            }
            for j in 0..grid[0].len() {
                if find {
                    break;
                }
                if grid[i][j] == 0 {
                    continue;
                }
                Self::dfs(&mut grid, i as i32, j as i32, &mut q);
                find = true;
            }
        }

        let mut step = 0;
        let (dx, dy) : ([i32; 4], [i32; 4]) = ([0, 0, 1, -1], [1, -1, 0, 0]);

        while !q.is_empty() {
            let mut size = q.len();
            while size > 0 {
                size -= 1;
                let item = q.front().unwrap().clone();
                q.pop_front();
                let (x, y) = (item.0, item.1);

                for i in 0..4 {
                    let (tx, ty) = (x + dx[i], y + dy[i]);
                    if tx < 0 || ty < 0 || ty >= grid[0].len() as i32 ||
                        tx >= grid.len() as i32 || grid[tx as usize][ty as usize] == 2 {
                        continue;
                    }
                    if grid[tx as usize][ty as usize] == 1 {
                        return step;
                    }
                    grid[tx as usize][ty as usize] = 2;
                    q.push_back((tx, ty));
                }
            }
            step += 1;
        }

        return -1;
    }
}

impl Solution {
    fn dfs(grid: &mut Vec<Vec<i32>>, x: i32, y: i32, n: i32) -> i32 {
        if x < 0 || x == grid[0].len() as i32 || y < 0 || y == grid.len() as i32 ||
            grid[y as usize][x as usize] == -1 {
            return 0;
        }
        let (yy, xx) = (y as usize, x as usize);
        if grid[yy][xx] == 2 {
            if n == 0 {
                return 1;
            } else {
                return 0;
            }
        }
        grid[yy][xx] = -1;
        let ans = Self::dfs(grid, x + 1, y, n - 1) +
            Self::dfs(grid, x - 1, y, n - 1) +
            Self::dfs(grid, x, y + 1, n - 1) +
            Self::dfs(grid, x, y - 1, n - 1);
        grid[yy][xx] = 0;
        return ans;
    }
    pub fn unique_paths_iii(grid: Vec<Vec<i32>>) -> i32 {
        let (mut sx, mut sy, mut n) = (0, 0, 1);
        let mut g = grid.clone();
        for i in 0..g.len() {
            for j in 0..g[0].len() {
                if g[i][j] == 0 {
                    n += 1;
                } else if grid[i][j] == 1 {
                    sx = j; sy = i;
                }
            }
        }

        return Self::dfs(&mut g, sx as i32, sy as i32, n);
    }
}

impl Solution {
    pub fn smallest_repunit_div_by_k(k: i32) -> i32 {
        let (mut cur, mut ans) = (1, 1);
        if k % 2 == 0 || k  % 5 == 0 {
            return -1;
        }

        while ans <= k {
            if cur % k == 0 {
                return ans;
            }
            cur = (cur * 10 + 1) % k;
            ans += 1;
        }
        return ans;
    }
}