use std::collections::VecDeque;

impl Solution {
    pub fn min_knight_moves(x: i32, y: i32) -> i32 {
        let (dx, dy) : ([i32; 8], [i32; 8]) = (
            [-2, -2, -1, -1, 1, 1, 2, 2],
            [-1, 1, -2, 2, -2, 2, -1, 1]);
        let mut grid = [[-1; 888] ; 888];
        let (ax, ay) = (x.abs() as usize, y.abs() as usize);
        grid[400][400] = 0;

        let mut q : VecDeque<(usize, usize)> = VecDeque::new();
        q.push_back((0, 0));
        while !q.is_empty() {
            let (cx, cy) = q.pop_front().unwrap();
            if cx == ax && cy == ay {
                return grid[cx + 400][cy + 400];
            }

            for k in 0..8 {
                let (xx, yy) = (cx as i32 + dx[k] , cy as i32 + dy[k]);
                let (nx, ny) = ((xx + 400) as usize, (yy + 400) as usize);
                if grid[nx][ny] != -1 {
                    continue;
                }
                grid[nx][ny] = grid[cx + 400][cy + 400] + 1;
                if xx as usize == ax && yy as usize == ay {
                    return grid[nx][ny];
                }
                q.push_back((xx as usize, yy as usize));
            }
        }

        return -1;
    }
}

use std::collections::HashMap;
use std::cmp;

impl Solution {
    pub fn longest_subsequence(arr: Vec<i32>, difference: i32) -> i32 {
        let (mut ans, mut map) = (0, HashMap::new());
        for i in arr {
            let val = cmp::max(*map.entry(i).or_insert(0),
                               *map.entry(i - difference).or_insert(0) + 1);
            map.insert(i, val);
            ans = cmp::max(ans, *map.entry(i).or_insert(0));
        }
        return ans;
    }
}

use std::collections::VecDeque;
use std::cmp;

impl Solution {
    pub fn get_maximum_gold(grid: Vec<Vec<i32>>) -> i32 {
        let (m, n, mut ans, mut id) = (grid.len(), grid[0].len(), 0, 0);
        let (dx, dy) : ([i32; 4], [i32; 4]) = ([0, 0, 1, -1], [1, -1, 0, 0]);
        let mut visited = vec![vec![0; n]; m];
        let mut q = VecDeque::new();

        for i in 0..m {
            for j in 0..n {
                if grid[i][j] == 0 {
                    continue;
                }
                id += 1;
                visited[i][j] = 1 << id;
                q.push_back((i, j, grid[i][j], visited[i][j]));
            }
        }

        while !q.is_empty() {
            let cur = q.pop_front().unwrap();
            let (x, y, sum, state) = (cur.0 as i32, cur.1 as i32, cur.2, cur.3);
            ans = cmp::max(ans, sum);
            for i in 0..4 {
                let (xx, yy) = (x + dx[i], y + dy[i]);
                if xx < 0 || xx == m as i32 || yy < 0 || yy == n as i32 ||
                    grid[xx as usize][yy as usize] == 0 || (state & visited[xx as usize][yy as usize] != 0) {
                    continue;
                }
                let (nx, ny) = (xx as usize, yy as usize);
                q.push_back((nx, ny, sum + grid[nx][ny], state | visited[nx][ny]));
            }
        }

        return ans;
    }
}