AtCoder Beginner Contest 332 D

https://atcoder.jp/contests/abc332/tasks/abc332_d

行と列の順列は独立なので、それぞれの順列と隣同士の互換がどれだけ要るかを計算しておけば、あとはしらみつぶしです。

// Swapping Puzzle
#![allow(non_snake_case)]

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()
}


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

fn read_input() -> (Vec<Vec<i32>>, Vec<Vec<i32>>) {
    let v = read_vec::<usize>();
    let H = v[0];
    let A: Vec<Vec<i32>> = (0..H).map(|_| read_vec::<i32>()).collect();
    let B: Vec<Vec<i32>> = (0..H).map(|_| read_vec::<i32>()).collect();
    (A, B)
}

type Perm = Vec<usize>;

fn collect_perms(N: usize) -> Vec<(Perm, usize)> {
    let hash = |perm: &Perm| -> usize {
        perm.iter().fold(0, |x, &y| x*N+y)
    };
    
    let nexts = |perm: &Perm| {
        (0..N-1).map(|i| {
                        let mut perm1 = perm.to_vec();
                        let tmp = perm1[i];
                        perm1[i] = perm1[i+1];
                        perm1[i+1] = tmp;
                        (perm1, i)
                    }).collect::<Vec<_>>()
    };
    
    let perm0: Perm = (0..N).collect();
    let mut result: HashMap<usize, (Perm, usize)> = HashMap::new();
    result.insert(hash(&perm0), (perm0.to_vec(), 0));
    let mut queue: VecDeque<(Perm, usize)> = VecDeque::new();
    queue.push_back((perm0, 0));
    while let Some((perm, size)) = queue.pop_front() {
        for (new_perm, _) in nexts(&perm).into_iter() {
            let h = hash(&new_perm);
            if !result.contains_key(&h) {
                result.insert(h, (new_perm.to_vec(), size+1));
                queue.push_back((new_perm, size+1))
            }
        }
    }
    let mut perms = result.into_iter().map(|(_, v)| v).collect::<Vec<_>>();
    perms.sort_by_key(|(_, s)| *s);
    perms
}

const INF: i32 = 1000;

fn is_coincident(perm1: &Perm, perm2: &Perm,
                    A: &Vec<Vec<i32>>, B: &Vec<Vec<i32>>) -> bool {
    for (i, &p1) in perm1.iter().enumerate() {
        for (j, &p2) in perm2.iter().enumerate() {
            if A[p1][p2] != B[i][j] {
                return false
            }
        }
    }
    true
}

fn F(A: Vec<Vec<i32>>, B: Vec<Vec<i32>>) -> i32 {
    let H = A.len();
    let W = A[0].len();
    let perms1 = collect_perms(H);
    let perms2 = collect_perms(W);
    let mut min_swaps = INF;
    for (perm1, n1) in perms1.iter() {
        for (perm2, n2) in perms2.iter() {
            let num_swaps = (*n1 + *n2) as i32;
            if num_swaps >= min_swaps {
                break
            }
            else if is_coincident(perm1, perm2, &A, &B) {
                min_swaps = num_swaps
            }
        }
    }
    if min_swaps == 1000 { -1 } else { min_swaps }
}

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