#![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(
    mut score: i64,
    sx: i64,
    sy: i64,
    dx: i64,
    dy: 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(val2) = lut.get(&(sx, sy)) {
        if *val2 < score {
            return 99999999999;
        }
    }
    lut.insert((sx, sy), score);

    let mut s = 99999999999;
    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, dx, dy, ex, ey, &m, lut);
        s = min(s, a);
    }

    x = sx + dy;
    y = sy + dx;
    if m[y as usize][x as usize] {
        let a = dfs(score + 1001, x, y, dy, dx, ex, ey, &m, lut);
        s = min(s, a);
    }

    x = sx - dy;
    y = sy - dx;
    if m[y as usize][x as usize] {
        let a = dfs(score + 1001, x, y, -dy, -dx, ex, ey, &m, lut);
        s = min(s, a);
    }

    return s;
}

fn get_paths(
    mut score: i64,
    fin: i64,
    mut path: Vec<(i64, i64)>,
    sx: i64,
    sy: i64,
    dx: i64,
    dy: i64,
    ex: i64,
    ey: i64,
    m: &Vec<Vec<bool>>,
    lut: &mut HashMap<(i64, i64), i64>,
    paths: &mut Vec<Vec<(i64, i64)>>,
) -> i64 {
    path.push((sx, sy));

    if sx == ex && sy == ey {
        paths.push(path);
        return score;
    }

    if score > fin {
        return 9999999999;
    }

    if let Some(best_score) = lut.get(&(sx, sy)) {
        if *best_score + 1001 < score {
            return 999999999;
        }
        if *best_score > score {
            lut.insert((sx, sy), score);
        }
    } else {
        lut.insert((sx, sy), score);
    }

    let mut s = 99999999999;
    let mut x = sx + dx;
    let mut y = sy + dy;
    if m[y as usize][x as usize] {
        let a = get_paths(score + 1, fin, path.clone(), x, y, dx, dy, ex, ey, m, lut, paths);
        s = min(s, a);
    }

    x = sx + dy;
    y = sy + dx;
    if m[y as usize][x as usize] {
        let a = get_paths(score + 1001, fin, path.clone(), x, y, dy, dx, ex, ey, m, lut, paths);
        s = min(s, a);
    }

    x = sx - dy;
    y = sy - dx;
    if m[y as usize][x as usize] {
        let a = get_paths(score + 1001, fin, path.clone(), x, y, -dy, -dx, ex, ey, m, lut, paths);
        s = min(s, a);
    }

    return s;
}

fn print(m: &Vec<Vec<bool>>, hs: &HashSet<(i64, i64)>) {
    for y in 0..m.len() {
        for x in 0..m[0].len() {
            if hs.contains(&(x as i64, y as i64)) {
                print!("O");
            } else if m[y][x] == 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 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 mut dx = 1;
    let mut dy = 0;

    let mut lut: HashMap<(i64, i64), i64> = HashMap::new();
    let res1 = dfs(0, sx, sy, dx, dy, ex, ey, &m, &mut lut);

    let mut lut: HashMap<(i64, i64), i64> = HashMap::new();
    let mut paths: Vec<Vec<(i64, i64)>> = Vec::new();
    get_paths(0, res1, vec![], sx, sy, dx, dy, ex, ey, &m, &mut lut, &mut paths);

    let mut hs: HashSet<(i64, i64)> = HashSet::new();
    for path in paths {
        for p in path {
            hs.insert(p);
        }
    }
    let res2 = hs.len();

    //print(&m, &hs);

    println!("res1: {}", res1);
    println!("res2: {}", res2);
    assert_eq!(res1, 114476);
    assert_eq!(res2, 508);
}