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

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

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

    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 m[y as usize][x as usize] {
            let a = dfs(score + 1, x, y, ex, ey, &m, lut);
            s = min(s, a);
        }
    }

    return s;
}

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 sx = 0;
    let mut sy = 0;
    let mut ex = 0;
    let mut ey = 0;
    let mut m: Vec<Vec<bool>> = Vec::new();
    for (y, line) in lines.enumerate() {
        let mut l: Vec<bool> = Vec::new();
        for (x, c) in line.chars().enumerate() {
            if c == '#' {
                l.push(false);
            } else {
                l.push(true);
            }
            if c == 'S' {
                sx = x as i64;
                sy = y as i64;
            } else if c == 'E' {
                ex = x as i64;
                ey = y as i64;
            }
        }
        //println!("{:?}", l);
        m.push(l);
    }
    let width = m.len();
    let height = m[0].len();

    let mut res1 = 0;
    let mut lut: HashMap<(i64, i64), i64> = HashMap::new();
    let ref_score = dfs(0, sx, sy, ex, ey, &m, &mut lut);
    for y in 1..height - 1 {
        for x in 1..width - 1 {
            if m[y][x] == true {
                continue;
            }
            let mut mc = m.clone();
            mc[y][x] = true;
            lut.clear();
            let score = dfs(0, sx, sy, ex, ey, &mc, &mut lut);
            if score + 100 <= ref_score {
                res1 += 1;
            }
        }
    }

    let mut from_start: HashMap<(i64, i64), i64> = HashMap::new();
    let mut to_end: HashMap<(i64, i64), i64> = HashMap::new();
    for y in 1..height - 1 {
        for x in 1..width - 1 {
            if m[y][x] == false {
                continue;
            }
            let x = x as i64;
            let y = y as i64;
            lut.clear();
            let score = dfs(0, sx, sy, x, y, &m, &mut lut);
            from_start.insert((x, y), score);

            lut.clear();
            let score = dfs(0, x, y, ex, ey, &m, &mut lut);
            to_end.insert((x, y), score);
        }
    }

    let mut res2 = 0;
    for y in 1..height - 1 {
        for x in 1..width - 1 {
            if m[y][x] == false {
                continue;
            }
            let x = x as i64;
            let y = y as i64;

            let s1 = from_start.get(&(x, y)).unwrap();
            for dx in -20..=20 {
                for dy in -20..=20 {
                    let s2 = (dx as i64).abs() + (dy as i64).abs();
                    if s2 > 20 {
                        continue;
                    }
                    if let Some(s3) = to_end.get(&(x + dx, y + dy)) {
                        if s1 + s2 + s3 + 100 <= ref_score {
                            res2 += 1;
                        }
                    }
                }
            }
        }
    }

    println!("res1: {}", res1);
    println!("res2: {}", res2);
    assert_eq!(res1, 1422);
    assert_eq!(res2, 1009299);
}