use std::env::args;
use std::fs::File;
use std::io::BufRead;
use std::io::BufReader;

fn wrap(i: u32) -> u32 {
    let mut j = i;
    while j > 9 {
        j -= 9;
    }
    return j;
}

fn propagate(mut totals: &mut Vec<u32>, map: &Vec<u32>, x: usize, y: usize, n: usize) {
    let i = y * n + x;
    let v = totals[i] + map[i];

    if x > 0 && v < totals[i - 1] {
        totals[i - 1] = v;
        propagate(&mut totals, &map, x - 1, y, n);
    }
    if y > 0 && v < totals[i - n] {
        totals[i - n] = v;
        propagate(&mut totals, &map, x, y - 1, n);
    }
    if x + 1 < n && v < totals[i + 1] {
        totals[i + 1] = v;
        propagate(&mut totals, &map, x + 1, y, n);
    }
    if y + 1 < n && v < totals[i + n] {
        totals[i + n] = v;
        propagate(&mut totals, &map, x, y + 1, n);
    }
}

fn main() {
    let path = args().nth(1).unwrap();
    let file = File::open(path).unwrap();

    let mut small_n = 0;
    let mut small_map = vec![];

    for line in BufReader::new(file).lines() {
        let l = line.unwrap();
        small_n += 1;
        for c in l.chars() {
            small_map.push(c.to_digit(10).unwrap());
        }
    }

    let n = small_n * 5;
    let mut map = vec![0; n * n];
    for small_y in 0..small_n {
        for small_x in 0..small_n {
            for dy in 0..5 {
                for dx in 0..5 {
                    let y = small_n * dy + small_y;
                    let x = small_n * dx + small_x;
                    map[y * n + x] = wrap(
                        small_map[small_y * small_n + small_x]
                        + (dx + dy) as u32
                    );
                }
            }
        }
    }

    let mut totals = vec![0; n * n];

    // It is most likely that fields to the bottom right have a smaller
    // total, so we first fill the map with these.
    //
    // This is not necessary for correctness, but allows us to save a
    // lot of work in the next step.
    for y in (0..n).rev() {
        for x in (0..n).rev() {
            let i = y * n + x;
            if y == n - 1 && x == n - 1 {
                totals[i] = 0;
            } else if y == n - 1 {
                totals[i] = totals[i + 1] + map[i + 1];
            } else if x == n - 1 {
                totals[i] = totals[i + n] + map[i + n];
            } else {
                totals[i] = std::cmp::min(
                    totals[i + 1] + map[i + 1],
                    totals[i + n] + map[i + n],
                );
            }
        }
    }
    println!("{}", totals[0]);

    // It is still possible that moving to the top or left yields a
    // shorter path, so we propagate these values to all direction.
    for y in 0..n {
        for x in 0..n {
            propagate(&mut totals, &map, x, y, n);
        }
    }
    println!("{}", totals[0]);
}