結果

問題 No.3679 なんかでっかい虫リターンズ
コンテスト
ユーザー yiwiy9
提出日時 2026-09-05 13:37:51
言語 Rust
(1.97.1 + proconio + num + itertools)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
AC  
実行時間 1 ms / 2,000 ms
+ 827µs
コード長 1,424 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 719 ms
コンパイル使用メモリ 181,948 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2026-09-05 13:37:58
合計ジャッジ時間 2,304 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

fn main() {
    input! {
        h: usize,
        w: usize,
        a: Usize1,
        b: Usize1,

        r1: Usize1,
        c1: Usize1,
        r2: Usize1,
        c2: Usize1,

        p: Usize1,
        q: Usize1,
    }

    let from_iwai_dist = grid_bfs(h, w, (a, b));
    let from_trash_dist = grid_bfs(h, w, (p, q));

    let mut ans = 1 << 60;
    for r in r1..=r2 {
        for c in c1..=c2 {
            ans = ans.min(from_iwai_dist[r][c] + from_trash_dist[r][c]);
        }
    }

    println!("{}", ans + from_trash_dist[a][b]);
}

pub fn grid_bfs(h: usize, w: usize, s: (usize, usize)) -> Vec<Vec<usize>> {
    let inf: usize = 1 << 30;
    let dx: [i32; 4] = [1, 0, -1, 0];
    let dy: [i32; 4] = [0, 1, 0, -1];
    let mut dist = vec![vec![inf; w]; h];
    let mut que = std::collections::VecDeque::new();
    dist[s.0][s.1] = 0;
    que.push_back(s);
    while let Some((x, y)) = que.pop_front() {
        for dir in 0..4 {
            let nx = x as i32 + dx[dir];
            let ny = y as i32 + dy[dir];
            if nx < 0 || h as i32 <= nx || ny < 0 || w as i32 <= ny {
                continue;
            }
            let nx = nx as usize;
            let ny = ny as usize;
            if dist[nx][ny] != inf {
                continue;
            }
            dist[nx][ny] = dist[x][y] + 1;
            que.push_back((nx, ny))
        }
    }
    dist
}
0