結果

問題 No.2986 Permutation Puzzle
ユーザー titiatitia
提出日時 2024-12-13 05:16:50
言語 Rust
(1.77.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 1 ms
6,816 KB
testcase_02 AC 6 ms
6,820 KB
testcase_03 AC 1,147 ms
171,820 KB
testcase_04 AC 1 ms
6,816 KB
testcase_05 AC 1 ms
6,816 KB
testcase_06 AC 1 ms
6,820 KB
testcase_07 AC 3 ms
6,820 KB
testcase_08 AC 6 ms
6,820 KB
testcase_09 AC 6 ms
6,816 KB
testcase_10 AC 5 ms
6,816 KB
testcase_11 AC 45 ms
11,620 KB
testcase_12 AC 56 ms
15,340 KB
testcase_13 AC 7 ms
6,816 KB
testcase_14 AC 10 ms
6,816 KB
testcase_15 AC 143 ms
34,772 KB
testcase_16 AC 3 ms
6,816 KB
testcase_17 AC 250 ms
40,168 KB
testcase_18 AC 348 ms
64,664 KB
testcase_19 AC 7 ms
6,820 KB
testcase_20 AC 254 ms
51,216 KB
testcase_21 AC 446 ms
98,148 KB
testcase_22 AC 4 ms
6,816 KB
testcase_23 AC 565 ms
92,924 KB
testcase_24 AC 792 ms
170,684 KB
testcase_25 AC 1,055 ms
173,292 KB
testcase_26 AC 1,095 ms
172,896 KB
testcase_27 AC 834 ms
172,004 KB
testcase_28 AC 1,082 ms
171,564 KB
testcase_29 AC 805 ms
171,952 KB
testcase_30 AC 1,013 ms
172,872 KB
testcase_31 AC 1,121 ms
172,384 KB
testcase_32 AC 1,139 ms
171,736 KB
testcase_33 AC 1,064 ms
171,208 KB
testcase_34 AC 1,082 ms
172,164 KB
testcase_35 AC 840 ms
172,636 KB
testcase_36 AC 1,002 ms
172,024 KB
testcase_37 AC 1,047 ms
171,768 KB
testcase_38 AC 1,085 ms
171,612 KB
testcase_39 AC 843 ms
171,488 KB
testcase_40 AC 1,155 ms
172,892 KB
testcase_41 AC 824 ms
171,580 KB
testcase_42 AC 1,046 ms
170,012 KB
testcase_43 AC 889 ms
172,792 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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