結果

問題 No.3599 Queen Moving Query
コンテスト
ユーザー urectanc
提出日時 2026-07-24 23:55:37
言語 Rust
(1.94.0 + proconio + num + itertools)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
AC  
実行時間 118 ms / 5,000 ms
+ 942µs
コード長 1,915 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 13,418 ms
コンパイル使用メモリ 192,552 KB
実行使用メモリ 50,432 KB
最終ジャッジ日時 2026-07-24 23:56:00
合計ジャッジ時間 13,182 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use std::collections::VecDeque;

use proconio::{
    fastout, input,
    marker::{Chars, Usize1},
};

#[fastout]
fn main() {
    input! {
        h: usize, w: usize,
        sx: Usize1, sy: Usize1,
        s: [Chars; h],
        q: usize,
        queries: [(Usize1, Usize1, usize); q],
    }

    let delta = [
        (-1, -1),
        (-1, 0),
        (-1, 1),
        (0, -1),
        (0, 1),
        (1, -1),
        (1, 0),
        (1, 1),
    ];
    let mut dist = vec![vec![[[!0usize; 2]; 8]; w]; h];
    let mut que = VecDeque::new();
    for dir in 0..8 {
        dist[sx][sy][dir][0] = 0;
        que.push_back((sx, sy, dir, 0));
    }

    let mut can_move = false;
    while let Some((i, j, dir, parity)) = que.pop_front() {
        let now = dist[i][j][dir][parity];
        for (ndir, &(di, dj)) in delta.iter().enumerate() {
            let ni = i.wrapping_add_signed(di);
            let nj = j.wrapping_add_signed(dj);
            if ni >= h || nj >= w || s[ni][nj] == '#' {
                continue;
            }

            if now != 0 && dir == ndir {
                let nparity = parity;
                if dist[ni][nj][ndir][nparity] == !0 {
                    dist[ni][nj][ndir][nparity] = now;
                    que.push_front((ni, nj, ndir, nparity));
                    can_move |= true;
                }
            }
            {
                let nparity = parity ^ 1;
                if dist[ni][nj][ndir][nparity] == !0 {
                    dist[ni][nj][ndir][nparity] = now + 1;
                    que.push_back((ni, nj, ndir, nparity));
                    can_move |= true;
                }
            }
        }
    }

    for &(gx, gy, t) in &queries {
        let parity = t % 2;
        let min = (0..8).map(|dir| dist[gx][gy][dir][parity]).min().unwrap();
        let ans = can_move && min <= t;
        println!("{}", if ans { "Yes" } else { "No" });
    }
}
0