use std::collections::HashMap;
use std::collections::VecDeque;

#[path = "../lib.rs"]
mod lib;

#[derive(Eq, PartialEq, Hash, Copy, Clone, Debug)]
enum Dir {
    Left,
    Right,
    Up,
    Down,
}

impl Dir {
    fn apply(&self, x: usize, y: usize, k: usize, n: usize) -> Option<(usize, usize)> {
        return match self {
            Dir::Left => if x >= k { Some((x - k, y)) } else { None }
            Dir::Right => if x + k < n { Some((x + k, y)) } else { None }
            Dir::Up => if y >= k { Some((x, y - k)) } else { None }
            Dir::Down => if y + k < n { Some((x, y + k)) } else { None }
        };
    }

    fn sides(&self) -> [Self; 2] {
        return match self {
            Dir::Left | Dir::Right => [Dir::Up, Dir::Down],
            Dir::Up | Dir::Down => [Dir::Left, Dir::Right],
        }
    }
}

fn parse_input() -> Vec<Vec<u32>> {
    return lib::iter_input()
        .map(|line| {
            return line.chars().map(|c| c.to_digit(10).unwrap()).collect();
        })
        .collect();
}

fn find_path(map: &Vec<Vec<u32>>, min_steps: usize, max_steps: usize) -> u32 {
    assert!(map.len() == map[0].len());
    let n = map.len();

    let mut queue = VecDeque::new();
    let mut min = HashMap::new();
    let mut result = u32::MAX;

    min.insert((0, 0, Dir::Right), 0);
    queue.push_back((0, 0, Dir::Right));

    min.insert((0, 0, Dir::Down), 0);
    queue.push_back((0, 0, Dir::Down));

    while let Some((y, x, dir)) = queue.pop_front() {
        let value = *min.get(&(y, x, dir)).unwrap_or(&u32::MAX);
        if (x, y) == (n - 1, n - 1) {
            result = result.min(value);
        }
        for ndir in dir.sides() {
            let mut new_value = value;
            for k in 1..=max_steps {
                if let Some((nx, ny)) = ndir.apply(x, y, k, n) {
                    new_value += map[ny][nx];
                    if k >= min_steps {
                        let key = (ny, nx, ndir);
                        if new_value < *min.get(&key).unwrap_or(&u32::MAX) {
                            min.insert(key, new_value);
                            queue.push_back(key);
                        }
                    }
                } else {
                    break;
                }
            }
        }
    }

    return result;
}

fn main() {
    let map = parse_input();

    println!("part1: {}", find_path(&map, 1, 3));
    println!("part2: {}", find_path(&map, 4, 10));
}