結果
問題 | No.2986 Permutation Puzzle |
ユーザー |
![]() |
提出日時 | 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
ソースコード
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); } }