結果
| 問題 | No.5006 Hidden Maze |
| ユーザー |
 sca1l
|
| 提出日時 | 2022-06-12 16:05:50 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 53 ms / 2,000 ms |
| コード長 | 6,603 bytes |
| コンパイル時間 | 986 ms |
| 実行使用メモリ | 22,868 KB |
| スコア | 0 |
| 平均クエリ数 | 1001.00 |
| 最終ジャッジ日時 | 2022-06-12 16:08:18 |
| 合計ジャッジ時間 | 10,545 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge16 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
コンパイルメッセージ
warning: constant `delta` should have an upper case name --> Main.rs:26:7 | 26 | const delta: Delta = Delta::new(); | ^^^^^ help: convert the identifier to upper case: `DELTA` | = note: `#[warn(non_upper_case_globals)]` on by default warning: 1 warning emitted
ソースコード
#![allow(non_snake_case, dead_code, unused_imports, unused_macros)]
use std::collections::VecDeque;
use std::collections::BinaryHeap;
use std::cmp::Reverse;
use std::cmp::Ordering;
use std::cmp::{max, min};
use std::io::{stdout, Write};
const N: usize = 20;
struct Delta {
pub y: [usize; 4],
pub x: [usize; 4],
pub d: [char; 4],
}
impl Delta {
const fn new() -> Self {
let y = [ !0, 0, 1, 0];
let x = [ 0, !0, 0, 1];
let d = ['U', 'L', 'D', 'R'];
Delta{ y, x, d }
}
}
const delta: Delta = Delta::new();
fn getline() -> String{
let mut __ret = String::new();
std::io::stdin().read_line(&mut __ret).ok();
return __ret;
}
#[derive(Clone)]
struct State {
pub move_cnt: Reverse<usize>,
pub last_pos: usize,
pub order: RcList<usize>,
}
impl State {
fn new() -> Self {
let move_cnt = Reverse(0);
let last_pos = 0;
let order = RcList::new();
State{ move_cnt, last_pos, order}
}
fn move_next(&self, dir: usize) -> Self {
let mut nproc = self.clone();
nproc.move_cnt = Reverse(nproc.move_cnt.0 + 1);
let ny = nproc.last_pos/N + delta.y[dir];
let nx = nproc.last_pos%N + delta.x[dir];
nproc.last_pos = ny*N+nx;
nproc.order.push(dir);
//
nproc
}
}
impl PartialOrd for State {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(&other))
}
}
impl Ord for State {
fn cmp(&self, other: &Self) -> Ordering {
self.move_cnt.cmp(&other.move_cnt)
}
}
impl PartialEq for State {
fn eq(&self, other: &Self) -> bool {
self.move_cnt == other.move_cnt
}
}
impl Eq for State {
//
}
fn solve() {
let mut visited_pos = [false; N*N];
visited_pos[0] = true;
let mut heap: BinaryHeap<State> = BinaryHeap::new();
heap.push(State::new());
let mut second_heap: BinaryHeap<State> = BinaryHeap::new();
'main: loop {
if let Some(proc) = heap.pop() {
let current_move_cnt = proc.move_cnt.0 as i32;
let cy = proc.last_pos/N;
let cx = proc.last_pos%N;
let order_vec = proc.order.to_vec();
for i in 0..4 {
let ny = cy + delta.y[i];
let nx = cx + delta.x[i];
if !within_board(ny, nx) {
continue;
}
if visited_pos[ny*N+nx] {
continue;
}
//ok
let mut cnt = 0;
loop {
{
for &dir in order_vec.iter() {
print!("{}", delta.d[dir]);
}
print!("{}", delta.d[i]);
println!();
stdout().flush().unwrap();
}
{
let line = getline();
let input: i32 = line.trim().parse().unwrap();
if input < 0 {
//have to exit
break 'main;
} else if input == current_move_cnt + 1 {
//success
let nproc = proc.move_next(i);
visited_pos[nproc.last_pos] = true;
heap.push(nproc);
break;
} else if input == current_move_cnt {
//there is wall (perhaps)
cnt += 1;
if cnt < 3 {
continue;
} else {
second_heap.push(proc.clone());
break;
}
} else if input < current_move_cnt {
//just unlucky
continue;
}
}
}
}
} else {
heap = second_heap;
second_heap = BinaryHeap::new();
}
}
//
}
fn main() {
let _ = getline();
solve();
}
fn within_board(y: usize, x:usize) -> bool {
y < N && x < N
}
fn manhattan_dist(ty: usize, tx: usize, py: usize, px: usize) -> usize {
diff_abs(ty, py) + diff_abs(tx, px)
}
fn diff_abs(a: usize, b: usize) -> usize {
max(a, b) - min(a, b)
}
//-----------------------------------------
#[derive(Debug)]
#[allow(dead_code)]
pub struct Xorshift {
seed: u64,
}
impl Xorshift {
#[allow(dead_code)]
pub fn new() -> Xorshift {
Xorshift {
seed: 0xf0fb588ca2196dac,
}
}
#[allow(dead_code)]
pub fn with_seed(seed: u64) -> Xorshift {
Xorshift { seed: seed }
}
#[inline]
#[allow(dead_code)]
pub fn next(&mut self) -> u64 {
self.seed = self.seed ^ (self.seed << 13);
self.seed = self.seed ^ (self.seed >> 7);
self.seed = self.seed ^ (self.seed << 17);
self.seed
}
#[inline]
#[allow(dead_code)]
pub fn rand_u64(&mut self, m: u64) -> u64 {
self.next() % m
}
#[inline]
#[allow(dead_code)]
pub fn rand(&mut self, m: usize) -> usize {
self.rand_u64(m as u64) as usize
}
#[inline]
#[allow(dead_code)]
// 0.0 ~ 1.0
pub fn randf(&mut self) -> f64 {
use std::mem;
const UPPER_MASK: u64 = 0x3FF0000000000000;
const LOWER_MASK: u64 = 0xFFFFFFFFFFFFF;
let tmp = UPPER_MASK | (self.next() & LOWER_MASK);
let result: f64 = unsafe { mem::transmute(tmp) };
result - 1.0
}
}
//------------------------------------
use std::rc::Rc;
#[derive(Debug)]
struct RcListInner<T> {
parent: RcList<T>,
value: T,
}
#[doc = "O(1) clone, O(1) push"]
#[derive(Clone, Debug)]
struct RcList<T>(Option<Rc<RcListInner<T>>>);
impl<T: Clone> RcList<T> {
#[allow(dead_code)]
fn new() -> Self {
RcList(None)
}
#[allow(dead_code)]
#[inline]
fn push(&mut self, value: T) {
*self = RcList(Some(Rc::new(RcListInner {
parent: self.clone(),
value,
})));
}
#[allow(dead_code)]
fn to_vec(&self) -> Vec<T> {
if let Some(ref inner) = self.0 {
let mut p = inner.parent.to_vec();
p.push(inner.value.clone());
p
} else {
Vec::new()
}
}
}
//-----------------------------------------