結果

問題 No.2986 Permutation Puzzle
ユーザー titia
提出日時 2024-12-13 05:16:50
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 1,155 ms / 2,000 ms
コード長 5,733 bytes
コンパイル時間 14,923 ms
コンパイル使用メモリ 403,400 KB
実行使用メモリ 173,292 KB
最終ジャッジ日時 2024-12-13 05:17:33
合計ジャッジ時間 39,052 ms
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused variable: `k`
  --> src/main.rs:67:9
   |
67 |     let k: usize = inputs.next().unwrap().parse().unwrap();
   |         ^ help: if this is intentional, prefix it with an underscore: `_k`
   |
   = note: `#[warn(unused_variables)]` on by default

ソースコード

diff #

use std::collections::{HashMap, VecDeque};
use std::io;

fn change(a: &Vec<i8>, command: &str, ind: usize, n: usize) -> Vec<i8> {
    let mut result = vec![0; n * n];

    if command == "R" {
        let mut a2: Vec<Vec<i8>> = vec![vec![0; n]; n];
        for i in 0..n {
            for j in 0..n {
                a2[i][j] = a[i * n + j];
            }
        }

        let mut c: Vec<Vec<i8>> = vec![vec![0; n]; n];
        for j in 0..n {
            c[(a2[ind - 1][j] - 1) as usize] = a2[j].clone();
        }

        for i in 0..n {
            for j in 0..n {
                result[i * n + j] = c[i][j];
            }
        }
    } else {
        let mut b = vec![0; n * n];
        for i in 0..n {
            for j in 0..n {
                b[i * n + j] = a[j * n + i];
            }
        }

        let mut b2: Vec<Vec<i8>> = vec![vec![0; n]; n];
        for i in 0..n {
            for j in 0..n {
                b2[i][j] = b[i * n + j];
            }
        }

        let mut c: Vec<Vec<i8>> = vec![vec![0; n]; n];
        for j in 0..n {
            c[(b2[ind - 1][j] - 1) as usize] = b2[j].clone();
        }

        let mut d = vec![0; n * n];
        for i in 0..n {
            for j in 0..n {
                d[i * n + j] = c[i][j];
            }
        }

        for i in 0..n {
            for j in 0..n {
                result[j * n + i] = d[i * n + j];
            }
        }
    }

    result
}

fn main() {
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    let mut inputs = input.trim().split_whitespace();
    let n: usize = inputs.next().unwrap().parse().unwrap();
    let k: usize = inputs.next().unwrap().parse().unwrap();

    let mut a = Vec::new();
    for _ in 0..n {
        input.clear();
        io::stdin().read_line(&mut input).unwrap();
        a.extend(input.trim().split_whitespace().map(|x| x.parse::<i8>().unwrap()));
    }

    let mut b = Vec::new();
    for _ in 0..n {
        input.clear();
        io::stdin().read_line(&mut input).unwrap();
        b.extend(input.trim().split_whitespace().map(|x| x.parse::<i8>().unwrap()));
    }

    let a0 = a.clone();
    let mut dict: HashMap<Vec<i8>, Vec<(String, usize)>> = HashMap::new();
    dict.insert(a.clone(), vec![]);

    let mut from: HashMap<Vec<i8>, (Vec<i8>, String, usize)> = HashMap::new();
    let mut q = VecDeque::new();
    q.push_back(a.clone());

    let mut flag = false;
    for _ in 0..4 {
        if flag {
            break;
        }

        let mut nq = VecDeque::new();
        while let Some(a) = q.pop_front() {
            if a == b {
                flag = true;
                break;
            }

            let ans = dict[&a].clone();
            for ind in 1..=n {
                for command in ["R", "C"] {
                    let a2 = change(&a, command, ind, n);
                    if !dict.contains_key(&a2) {
                        let mut ans2 = ans.clone();
                        ans2.push((command.to_string(), ind));
                        dict.insert(a2.clone(), ans2);
                        from.insert(a2.clone(), (a.clone(), command.to_string(), ind));
                        nq.push_back(a2);
                    }
                }
            }
        }
        q = nq;
    }

    let mut b = b.clone();
    let mut ans = Vec::new();

    while b != a0 {
        let (fr, com, ind) = from[&b].clone();
        if com == "R" {
            let mut fr2: Vec<Vec<i8>> = vec![vec![0; n]; n];
            for i in 0..n {
                for j in 0..n {
                    fr2[i][j] = fr[i * n + j];
                }
            }

            let need = fr2[ind - 1].clone();

            while b != fr {
                let mut b2: Vec<Vec<i8>> = vec![vec![0; n]; n];
                for i in 0..n {
                    for j in 0..n {
                        b2[i][j] = b[i * n + j];
                    }
                }

                for i in 0..n {
                    if b2[i] == need {
                        ans.push(("R".to_string(), i + 1));
                        b = change(&b, "R", i + 1, n);
                        break;
                    }
                }
            }
        } else {
            let mut b2 = vec![0; n * n];
            for i in 0..n {
                for j in 0..n {
                    b2[i * n + j] = b[j * n + i];
                }
            }

            let mut fr2 = vec![0; n * n];
            for i in 0..n {
                for j in 0..n {
                    fr2[i * n + j] = fr[j * n + i];
                }
            }

            b = b2;
            let mut fr2_vec: Vec<Vec<i8>> = vec![vec![0; n]; n];
            for i in 0..n {
                for j in 0..n {
                    fr2_vec[i][j] = fr2[i * n + j];
                }
            }

            let need = fr2_vec[ind - 1].clone();

            while b != fr2 {
                let mut b2_vec: Vec<Vec<i8>> = vec![vec![0; n]; n];
                for i in 0..n {
                    for j in 0..n {
                        b2_vec[i][j] = b[i * n + j];
                    }
                }

                for i in 0..n {
                    if b2_vec[i] == need {
                        ans.push(("C".to_string(), i + 1));
                        b = change(&b, "R", i + 1, n);
                        break;
                    }
                }
            }

            let mut b2 = vec![0; n * n];
            for i in 0..n {
                for j in 0..n {
                    b2[i * n + j] = b[j * n + i];
                }
            }
            b = b2;
        }
    }

    println!("{}", ans.len());
    for (com, ind) in ans {
        println!("{} {}", com, ind);
    }
}
0