結果

問題 No.2228 Creeping Ghost
ユーザー atcoder8
提出日時 2023-02-25 00:50:05
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 122 ms / 2,000 ms
コード長 3,209 bytes
コンパイル時間 13,089 ms
コンパイル使用メモリ 388,664 KB
実行使用メモリ 8,076 KB
最終ジャッジ日時 2024-09-13 06:29:55
合計ジャッジ時間 14,628 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

const SIDE_LEN: usize = 5;
const DIFFS: [(usize, usize, char); 4] = [(!0, 0, 'U'), (0, !0, 'L'), (0, 1, 'R'), (1, 0, 'D')];
fn main() {
    let t = {
        let mut line = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
        line.trim().parse::<usize>().unwrap()
    };
    let dfs = |self_coord: (usize, usize), ghost_coord: (usize, usize)| {
        let mut stack = vec![(self_coord, vec![])];
        while let Some((cur_self_coord, cur_move)) = stack.pop() {
            if cur_move.len() == 3 {
                if !is_checkmate(cur_self_coord, ghost_coord) {
                    return Some((cur_self_coord, cur_move));
                } else {
                    continue;
                }
            }
            let (cur_self_x, cur_self_y) = cur_self_coord;
            for &(diff_x, diff_y, dir) in &DIFFS {
                let next_self_x = cur_self_x.wrapping_add(diff_x);
                let next_self_y = cur_self_y.wrapping_add(diff_y);
                if next_self_x >= SIDE_LEN || next_self_y >= SIDE_LEN {
                    continue;
                }
                let next_self_coord = (next_self_x, next_self_y);
                if !is_found(next_self_coord, ghost_coord) {
                    let mut next_move = cur_move.clone();
                    next_move.push(dir);
                    stack.push((next_self_coord, next_move));
                }
            }
        }
        None
    };
    let mut history = ['R', 'L', 'R'].to_vec();
    let mut prev_coord = (0, 0);
    let mut cur_coord = (0_usize, 1_usize);
    while history.len() < 1_000_000 {
        let (cur_x, cur_y) = cur_coord;
        for (diff_x, diff_y, dir) in DIFFS {
            let next_x = cur_x.wrapping_add(diff_x);
            let next_y = cur_y.wrapping_add(diff_y);
            if next_x >= SIDE_LEN || next_y >= SIDE_LEN {
                continue;
            }
            let next_coord = (next_x, next_y);
            if !is_found(next_coord, prev_coord) {
                if let Some((moved_coord, mut move_log)) = dfs(next_coord, prev_coord) {
                    prev_coord = next_coord;
                    cur_coord = moved_coord;
                    history.push(dir);
                    history.append(&mut move_log);
                    break;
                }
            }
        }
    }
    let ans: String = history.iter().take(t).collect();
    println!("{}", ans);
}
fn is_corner(coord: (usize, usize)) -> bool {
    let (x, y) = coord;
    (x == 0 || x == SIDE_LEN - 1) && (y == 0 || y == SIDE_LEN - 1)
}
fn abs_diff(x: usize, y: usize) -> usize {
    if x >= y {
        x - y
    } else {
        y - x
    }
}
fn check_diagonally_adjacent(coord1: (usize, usize), coord2: (usize, usize)) -> bool {
    let (x1, y1) = coord1;
    let (x2, y2) = coord2;
    abs_diff(x1, x2) == 1 && abs_diff(y1, y2) == 1
}
fn is_checkmate(this_coord: (usize, usize), ghost_coord: (usize, usize)) -> bool {
    is_corner(this_coord) && check_diagonally_adjacent(this_coord, ghost_coord)
}
fn is_found(this_coord: (usize, usize), ghost_coord: (usize, usize)) -> bool {
    this_coord.0 == ghost_coord.0 || this_coord.1 == ghost_coord.1
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0