use std::cmp::Reverse;
use std::collections::BinaryHeap;
use std::collections::HashMap;
const N: usize = 200;
const M: usize = 200;

pub fn dist(input: &Vec<Vec<u32>>, y1: i32, x1: i32, y2: i32, x2: i32) -> i32 {
    let ind1 = (y1 - y2).abs();
    let ind2 = (x1 - x2).abs();

    if (ind1 == 1 && ind2 == 0) || (ind1 == 0 && ind2 == 1) {
        return input[y2 as usize][x2 as usize] as i32;
    }

    return i32::MAX;
}

pub fn main() {
    let txt = std::fs::read_to_string("./input/day17.txt").unwrap();
    let input = txt
        .lines()
        .map(|s| {
            s.split("")
                .filter_map(|c| c.parse::<u32>().ok())
                .collect::<Vec<_>>()
        })
        .collect::<Vec<Vec<_>>>();

    let n = input.len();
    let m = input[0].len();
    let mut d = [[i32::MAX; M]; N];

    // (dist, y, x, dy, dx, cnt)
    let mut bh: BinaryHeap<Reverse<(i32, i32, i32, i32, i32, i32)>> = Default::default();
    // (y, x, dy, dx, cnt)
    let mut hm: HashMap<(i32, i32, i32, i32, i32), bool> = Default::default();

    bh.push(Reverse((0, 0, 0, 0, 1, 0)));
    bh.push(Reverse((0, 0, 0, 1, 0, 0)));
    hm.insert((0, 0, 0, 1, 0), true);
    hm.insert((0, 0, 1, 0, 0), true);

    while !bh.is_empty() {
        let Reverse(x) = bh.pop().unwrap();
        let (ndist, i, j, odi, odj, cnt) = x;

        if ndist < d[i as usize][j as usize] && cnt >= 4 {
            d[i as usize][j as usize] = ndist;
        }

        for (di, dj) in [(0, 1), (0, -1), (1, 0), (-1, 0)] {
            if odi == -di && odj == -dj {
                continue;
            }

            if cnt < 4 && !(odi == di && odj == dj) {
                continue;
            }

            let ni = i + di;
            let nj = j + dj;
            if ni < 0 || ni >= n as i32 || nj < 0 || nj >= m as i32 {
                continue;
            }

            let ncnt = if di == odi && dj == odj { cnt + 1 } else { 1 };
            let ndst = ndist + dist(&input, i, j, ni, nj);

            if hm.contains_key(&(ni, nj, di, dj, ncnt)) || ncnt == 11 {
                continue;
            } else {
                hm.insert((ni, nj, di, dj, ncnt), true);
            }

            bh.push(Reverse((ndst, ni, nj, di, dj, ncnt)));
        }
    }

    println!("{}", d[n - 1][m - 1]);
}