結果

問題 No.2228 Creeping Ghost
ユーザー atcoder8atcoder8
提出日時 2023-02-25 00:50:05
言語 Rust
(1.77.0)
結果
AC  
実行時間 121 ms / 2,000 ms
コード長 3,209 bytes
コンパイル時間 1,214 ms
コンパイル使用メモリ 148,656 KB
実行使用メモリ 8,280 KB
最終ジャッジ日時 2023-10-11 07:21:14
合計ジャッジ時間 3,813 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 115 ms
6,012 KB
testcase_01 AC 116 ms
5,988 KB
testcase_02 AC 116 ms
5,988 KB
testcase_03 AC 116 ms
5,944 KB
testcase_04 AC 116 ms
7,456 KB
testcase_05 AC 120 ms
8,280 KB
testcase_06 AC 119 ms
6,500 KB
testcase_07 AC 121 ms
6,736 KB
testcase_08 AC 120 ms
6,736 KB
testcase_09 AC 118 ms
6,496 KB
testcase_10 AC 120 ms
6,492 KB
権限があれば一括ダウンロードができます

ソースコード

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
}
0