AtCoder Beginner Contest 323 F

https://atcoder.jp/contests/abc323/tasks/abc323_f

場合分けすればなんとかなりそうですが、場合がものすごく多そうですよね。そこで、A、B、Cの位置関係を変えずに圧縮して、移動回数を数えて、圧縮した分を足せばよいです。

// Push and Carry
#![allow(non_snake_case)]

use std::ops::{Add, Sub};
use std::collections::{HashMap, VecDeque};


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// Point ////////////////////

#[derive(Clone, Copy)]
#[derive(PartialEq, Eq, Hash)]
struct Point {
    x: i64,
    y: i64,
}

impl Add for Point {
    type Output = Self;
    
    fn add(self, other: Self) -> Self {
        Self { x: self.x + other.x, y: self.y + other.y }
    }
}

impl Sub for Point {
    type Output = Self;
    
    fn sub(self, other: Self) -> Self {
        Self { x: self.x - other.x, y: self.y - other.y }
    }
}

impl Point {
    fn new(x: i64, y: i64) -> Point {
        Point { x, y }
    }
}


//////////////////// process ////////////////////

fn read_input() -> (Point, Point, Point) {
    let v = read_vec();
    let A = Point::new(v[0], v[1]);
    let B = Point::new(v[2], v[3]);
    let C = Point::new(v[4], v[5]);
    (A, B, C)
}

fn comp(x1: i64, x2: i64) -> i64 {
    if x1 == x2 {
        0
    }
    else if x1 < x2 {
        1
    }
    else {
        -1
    }
}

fn compress_each(xA: i64, xB: i64, xC: i64) -> (i64, i64) {
    let mut v: Vec<(i64, i64)> = vec![(xA, 0), (xB, 1), (xC, 2)];
    v.sort();
    let d1 = comp(v[0].0, v[1].0);
    let d2 = comp(v[1].0, v[2].0);
    let mut w: Vec<(i64, i64)> = vec![(0, v[0].1), (d1, v[1].1),
                                                    (d1+d2, v[2].1)];
    w.sort_by_key(|&(_, i)| i);
    (w[0].0 - w[2].0, w[1].0 - w[2].0)
}

fn compress(A: Point, B: Point, C: Point) -> (Point, Point) {
    let (xA, xB) = compress_each(A.x, B.x, C.x);
    let (yA, yB) = compress_each(A.y, B.y, C.y);
    (Point::new(xA, yA), Point::new(xB, yB))
}

type State = (Point, Point);

fn nexts((A, B): State) -> Vec<State> {
    let dirs: Vec<Point> = vec![Point::new(1, 0), Point::new(0, 1),
                                Point::new(-1, 0), Point::new(0, -1)];
    let mut states: Vec<State> = vec![];
    for &dir in dirs.iter() {
        let A1 = A + dir;
        if A1 == B {
            let B1 = B + dir;
            states.push((A1, B1))
        }
        else {
            states.push((A1, B))
        }
    }
    states
}

fn find_shortest_path(A: Point, B: Point) -> i64 {
    let C = Point::new(0, 0);
    let mut dp: HashMap<State, i64> = HashMap::new();
    dp.insert((A, B), 0);
    let mut queue: VecDeque<State> = VecDeque::new();
    queue.push_back((A, B));
    while let Some(state) = queue.pop_front() {
        let d = *dp.get(&state).unwrap();
        let next_states: Vec<State> = nexts(state).into_iter().
                                    filter(|s| !dp.contains_key(s)).collect();
        for &neigh in next_states.iter() {
            if neigh.1 ==  C {
                return d + 1
            }
            dp.insert(neigh, d + 1);
            queue.push_back(neigh)
        }
    }
    0
}

fn F(A: Point, B: Point, C: Point) -> i64 {
    let (new_A, new_B) = compress(A, B, C);
    let new_C = Point::new(0, 0);
    let d = find_shortest_path(new_A, new_B);
    let dxAB = (B.x - A.x).abs() - (new_B.x - new_A.x).abs();
    let dxBC = (C.x - B.x).abs() - (new_C.x - new_B.x).abs();
    let dyAB = (B.y - A.y).abs() - (new_B.y - new_A.y).abs();
    let dyBC = (C.y - B.y).abs() - (new_C.y - new_B.y).abs();
    d + dxAB + dxBC + dyAB + dyBC
}

fn main() {
    let (A, B, C) = read_input();
    println!("{}", F(A, B, C))
}