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

const LEN: usize = 23;

// #############
// #01.2.3.4.56#
// ###7#8#9#0###
//   #1#2#3#4#
//   #5#6#7#8#
//   #9#0#1#2#
//   #########

fn i2xy(i: usize) -> (i64, i64) {
    match i {
        0 => (1, 1),
        1 => (2, 1),
        2 => (4, 1),
        3 => (6, 1),
        4 => (8, 1),
        5 => (10, 1),
        6 => (11, 1),
        7 => (3, 2),
        8 => (5, 2),
        9 => (7, 2),
        10 => (9, 2),
        11 => (3, 3),
        12 => (5, 3),
        13 => (7, 3),
        14 => (9, 3),
        15 => (3, 4),
        16 => (5, 4),
        17 => (7, 4),
        18 => (9, 4),
        19 => (3, 5),
        20 => (5, 5),
        21 => (7, 5),
        22 => (9, 5),
        _ => unreachable!(),
    }
}

fn xy2i(x: i64, y: i64) -> Option<usize> {
    match (x, y) {
        (1, 1) => Some(0),
        (2, 1) => Some(1),
        (4, 1) => Some(2),
        (6, 1) => Some(3),
        (8, 1) => Some(4),
        (10, 1) => Some(5),
        (11, 1) => Some(6),
        (3, 2) => Some(7),
        (5, 2) => Some(8),
        (7, 2) => Some(9),
        (9, 2) => Some(10),
        (3, 3) => Some(11),
        (5, 3) => Some(12),
        (7, 3) => Some(13),
        (9, 3) => Some(14),
        (3, 4) => Some(15),
        (5, 4) => Some(16),
        (7, 4) => Some(17),
        (9, 4) => Some(18),
        (3, 5) => Some(19),
        (5, 5) => Some(20),
        (7, 5) => Some(21),
        (9, 5) => Some(22),
        _ => None,
    }
}

fn path_steps(i: usize, j: usize) -> i64 {
    let (x1, y1) = i2xy(i);
    let (x2, y2) = i2xy(j);
    if x1 == x2 {
        return (y1 - y2).abs();
    } else {
        return (x1 - x2).abs() + (y1 - 1).abs() + (y2 - 1).abs();
    }
}

fn path_free(map: &[u8; LEN], i: usize, j: usize) -> bool {
    let (x1, y1) = i2xy(i);
    let (x2, y2) = i2xy(j);

    for y in 2..y1 {
        if map[xy2i(x1, y).unwrap()] != 0 {
            return false;
        }
    }
    for y in 2..y2 {
        if map[xy2i(x2, y).unwrap()] != 0 {
            return false;
        }
    }

    let (x_min, x_max) = if x1 < x2 {(x1, x2)} else {(x2, x1)};
    for x in x_min+1..x_max {
        match xy2i(x, 1) {
            Some(a) => if map[a] != 0 {
                return false;
            },
            None => {},
        }
    }

    return true
}

fn is_final_position(map: &[u8; LEN], c: u8, x: i64, y: i64) -> bool {
    if y == 1 {
        return false;
    }
    if x / 2 != i64::from(c) {
        return false;
    }
    for yy in y+1.. {
        match xy2i(x, yy) {
            Some(a) => if map[a] != c {
                return false;
            },
            None => break,
        }
    }
    return true;
}

fn legal_move(map: &[u8; LEN], i: usize, j: usize) -> bool {
    if map[j] != 0 {
        return false;
    }

    let (x1, y1) = i2xy(i);
    let (x2, y2) = i2xy(j);

    // cannot move from hallway to hallway
    if y1 == 1 && y2 == 1 {
        return false;
    }

    if y2 > 1 && !is_final_position(map, map[i], x2, y2) {
        return false;
    }

    if is_final_position(map, map[i], x1, y1) {
        return false;
    }

    if !path_free(map, i, j) {
        return false;
    }

    return true;
}

fn get_input() -> ([u8; LEN], [u8; LEN]) {
    let path = args().nth(1).unwrap();
    let file = File::open(path).unwrap();

    let mut map = [0; LEN];
    let mut target = [0; LEN];

    for (y, line) in BufReader::new(file).lines().enumerate() {
        for (x, c) in line.unwrap().chars().enumerate() {
            match (xy2i(x as i64, y as i64), c)  {
                (Some(i), 'A') => map[i] = 1,
                (Some(i), 'B') => map[i] = 2,
                (Some(i), 'C') => map[i] = 3,
                (Some(i), 'D') => map[i] = 4,
                _ => {},
            }
        }
    }

    for c in 1..=4 {
        for y in 2.. {
            match xy2i(c * 2 + 1, y) {
                Some(i) => target[i] = c as u8,
                None => break,
            }
        }
    }

    return (map, target);
}

fn legal_steps(map: &[u8; LEN]) -> Vec<([u8; LEN], i64)> {
    let mut steps = vec![];
    for i in 0..LEN {
        if map[i] != 0 {
            for j in 0..LEN {
                if legal_move(&map, i, j) {
                    let mut m = map.clone();
                    m[j] = map[i];
                    m[i] = 0;
                    let e = path_steps(i, j) * 10i64.pow(u32::from(map[i]) - 1);
                    steps.push((m, e));
                }
            }
        }
    }
    return steps;
}

fn estimate(map: &[u8; LEN]) -> i64 {
    // lower bound for required energy
    let mut required = 0;
    for i in 0..LEN {
        let (x, y) = i2xy(i);
        if map[i] != 0 && !is_final_position(map, map[i], x, y) {
            let j = xy2i(i64::from(map[i]) * 2 + 1, 2).unwrap();
            required += path_steps(i, j) * 10i64.pow(u32::from(map[i]) - 1);
        }
    }
    return required;
}

fn better(a: i64, b: Option<&i64>) -> bool {
    match b {
        Some(bb) => a < *bb,
        None => true,
    }
}

fn main() {
    let (initial, target) = get_input();
    let mut queue = vec![];
    let mut energies = HashMap::new();

    queue.push((initial, 0));
    energies.insert(initial, 0);

    while queue.len() > 0 {
        let (map, _) = queue.pop().unwrap();
        for (m, e_new) in legal_steps(&map) {
            let e = e_new + energies.get(&map).unwrap();
            let ee = e + estimate(&m);
            if better(e, energies.get(&m)) && better(ee, energies.get(&target)) {
                energies.insert(m, e);
                if m == target {
                    queue = queue.into_iter().filter(|(_map, ee_old)| *ee_old < e).collect();
                } else {
                    match queue.binary_search_by_key(&ee, |(_map, ee_old)| -ee_old) {
                        Ok(i) => queue.insert(i, (m, ee)),
                        Err(i) => queue.insert(i, (m, ee)),
                    }
                }
            }
        }
    }

    println!("{}", energies.get(&target).unwrap());
}