use std::collections::HashMap;

impl Solution {
    pub fn longest_arith_seq_length(a: Vec<i32>) -> i32 {
        let mut dp: HashMap<i32, HashMap<usize, i32>> = HashMap::new();
        let mut ans = 2;
        for i in 0..a.len() {
            for j in i + 1..a.len() {
                let d = a[j] - a[i];
                dp.entry(d).or_insert(HashMap::new());
                let val = dp.get_mut(&d).unwrap();
                let insert_val ;
                if val.contains_key(&i) {
                    insert_val = val.get(&i).unwrap().clone() + 1;
                } else {
                    insert_val = 2;
                }
                val.insert(j, insert_val);
                ans = std::cmp::max(ans, insert_val);
            }
        }

        return ans;
    }
}

impl Solution {
    pub fn num_moves_stones(a: i32, b: i32, c: i32) -> Vec<i32> {
        let mut input = vec![a, b, c];
        input.sort();
        if input[2] - input[0] == 2 {
            return vec![0, 0];
        }
        let max = input[2] - input[0] - 2;
        if std::cmp::min(input[1] - input[0], input[2] - input[1]) <= 2 {
            return vec![1, max];
        } else {
            return vec![2, max];
        }
    }
}

use std::collections::{HashSet, VecDeque};

impl Solution {
    fn search(blocked: &Vec<Vec<i32>>, source: &Vec<i32>, target: &Vec<i32>) ->bool {
        const M : i32 = 1000000;
        let (mut block, mut visited) =
            (HashSet::new(), HashSet::new());
        let (dx, dy) : ([i32; 4], [i32; 4]) = ([0, 0, 1, -1], [1, -1, 0, 0]);
        for i in blocked {
            block.insert((i[0], i[1]));
        }
        let mut q = VecDeque::new();
        q.push_back((source[0], source[1]));
        visited.insert((source[0], source[1]));

        while !q.is_empty() {
            if visited.len() > block.len() * block.len() / 2 {

                return true;
            }
            let cur = q.front().unwrap().clone(); q.pop_front();
            let (x, y) = (cur.0, cur.1);
            if x == target[0] && y == target[1] {
                return true;
            }
            for i in 0..4 {
                let (xx, yy) = (x + dx[i], y + dy[i]);
                if xx < 0 || yy < 0 || xx >= M || yy >= M || visited.contains(&(xx, yy))
                    || block.contains(&(xx, yy)) {
                    continue;
                }
                q.push_back((xx, yy));
                visited.insert((xx, yy));
            }
        }

        return false;
    }

    pub fn is_escape_possible(blocked: Vec<Vec<i32>>, source: Vec<i32>, target: Vec<i32>) -> bool {
        return Self::search(&blocked, &source, &target) &&
            Self::search(&blocked, &target, &source);
    }
}