結果
| 問題 |
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
ソースコード
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);
}
}