#![allow(dead_code)]
#![allow(unused_variables)]
#![allow(unused_mut)]
use std::cmp::min;
use std::collections::HashMap;
use std::collections::HashSet;
use std::env;
use std::fs::File;
use std::io::Read;

fn dfs(
    depth: i64,
    sx: i64,
    sy: i64,
    size: i64,
    m: &Vec<Vec<bool>>,
    lut: &mut HashMap<(i64, i64), i64>,
) -> i64 {
    if sx == size - 1 && sy == size - 1 {
        return depth;
    }

    if let Some(val) = lut.get(&(sx, sy)) {
        if *val < depth {
            return 99999999999;
        }
    }
    lut.insert((sx, sy), depth);

    let mut s = 99999999999;

    for (dx, dy) in [(1, 0), (-1, 0), (0, 1), (0, -1)] {
        let mut x = sx + dx;
        let mut y = sy + dy;
        if 0 <= x && x < size && 0 <= y && y < size {
            if m[y as usize][x as usize] {
                let a = dfs(depth + 1, x, y, size, &m, lut);
                s = min(s, a);
            }
        }
    }

    return s;
}

fn bfs(size: i64, m: &Vec<Vec<bool>>) -> i64 {
    let mut new_pos: HashSet<(i64, i64)> = HashSet::new();
    let mut all_pos: HashSet<(i64, i64)> = HashSet::new();
    let mut cur_pos: HashSet<(i64, i64)>;

    new_pos.insert((0, 0));

    all_pos = &all_pos | &new_pos;
    cur_pos = new_pos.clone();
    new_pos.clear();

    for depth in 0.. {
        for (sx, sy) in cur_pos.clone() {
            for (dx, dy) in [(1, 0), (-1, 0), (0, 1), (0, -1)] {
                let mut x = sx + dx;
                let mut y = sy + dy;
                if sx == size - 1 && sy == size - 1 {
                    return depth;
                }
                if 0 <= x && x < size && 0 <= y && y < size {
                    if m[y as usize][x as usize] {
                        if !all_pos.contains(&(x, y)) {
                            new_pos.insert((x, y));
                        }
                    }
                }
            }
        }
        if new_pos.len() == 0 {
            return 0;
        }
        all_pos = &all_pos | &new_pos;
        cur_pos = new_pos.clone();
        new_pos.clear();
    }

    return 0;
}

fn print_m(m: &Vec<Vec<bool>>) {
    for l in m {
        for c in l {
            if *c == true {
                print!(".");
            } else {
                print!("#");
            }
        }
        println!();
    }
}

fn main() {
    let args: Vec<String> = env::args().collect();
    let filename = if args.len() == 1 {
        "in/".to_owned() + args[0].split('/').last().unwrap() + ".pzl"
    } else {
        args[1].clone()
    };
    let mut f = File::open(filename).expect("cannot open file");
    let mut content = String::new();
    f.read_to_string(&mut content).expect("cannot read file");
    let lines = content.trim_end().split("\n");

    let mut bytes: Vec<(i64, i64)> = Vec::new();
    for line in lines {
        let (a, b) = line.split_once(',').unwrap();
        bytes.push((a.parse().unwrap(), b.parse().unwrap()));
    }
    //println!("{:?}", bytes);

    //let size = 6 + 1;
    //let mut fall = 12;
    let size = 70 + 1;
    let mut fall = 1024;

    let mut m: Vec<Vec<bool>> = vec![vec![true; size]; size];
    for i in 0..fall {
        let x = bytes[i].0 as usize;
        let y = bytes[i].1 as usize;
        m[y][x] = false;
    }
    //print_m(&m);

    let mut lut: HashMap<(i64, i64), i64> = HashMap::new();
    //let res1 = dfs(0, 0, 0, size as i64, &m, &mut lut);
    let res1 = bfs(size as i64, &m);

    let mut res2;
    loop {
        let x = bytes[fall].0 as usize;
        let y = bytes[fall].1 as usize;
        m[y][x] = false;
        fall += 1;
        let res = bfs(size as i64, &m);
        if res == 0 {
            res2 = format!("{},{}", x, y);
            break;
        }
    }

    println!("res1: {}", res1);
    println!("res2: {}", res2);
    assert_eq!(res1, 324);
    assert_eq!(res2, "46,23");
}