【競技プログラミング】Rust でグリッドグラフの走査

まえがき

競技プログラミングで、グリッドグラフが与えられて、隣接 4 マスに移動できる設定はよくあります。 そのときは以下のようなプログラムを書くことになると思います。くわしくはこの問題 https://atcoder.jp/contests/abc007/tasks/abc007_3 を見てください。

q = queue()
q.push((si, sj))
while len(q) > 0:
    i, j = q.pop()
    for di, dj in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
        ni, nj = i + di, j + dj
        if (ni, nj) が範囲内 && (ni, nj) が空きマス:
            # 何かする
            q.push((ni, nj))

上の問題の Python3 での回答例です: Submission #17943325 - AtCoder Beginner Contest 007

一方、Rust での回答例がこちらです: Submission #17943842 - AtCoder Beginner Contest 007
以下は隣接マスの走査パートを抜き出したコード片です。

• isize と usize との演算・比較はできない
• スライス a に対して a[x] としたいとき x は usize 型でないといけない (isize だとダメ)

という理由で型キャスト as isize, as usize を無限回書く必要があり、つらいです。

let dydx = [(-1, 0), (0, -1), (1, 0), (0, 1)];
let mut q = std::collections::VecDeque::new();
// ...
while let Some((y, x)) = q.pop_front() {
    for (dy, dx) in &dydx {
        let ny = y as isize + dy;
        let nx = x as isize + dx;
        if 0 <= ny && ny < R as isize && 0 <= nx && nx < C as isize {
            let ny = ny as usize;
            let nx = nx as usize;
            if a[ny][nx] == '.' && d[ny][nx] == -1 {
                // ...
            }
        }
    }
}

隣接マスを走査するライブラリ

「移動先のうち、グリッドの範囲内に収まるマス」を列挙するパートはライブラリ化しておきましょう。

Adjacent::new に

• 現在位置の座標
• グリッドの高さ (縦方向のマスの個数)
• グリッドの幅 (横方向のマスの個数)
• 移動先の座標との差分 (移りたいマスへのベクトル) 列

を渡します。

let dydx = [(-1, 0), (0, -1), (1, 0), (0, 1)];
let mut q = std::collections::VecDeque::new();
// ...
while let Some((y, x)) = q.pop_front() {
    for (ny, nx) in Adjacent::new((y, x), R, C, dydx.iter().copied()) {
        if a[ny][nx] == '.' && d[ny][nx] == -1 {
            // ...
        }
    }
}

ソースコードの全体は Submission #17944643 - AtCoder Beginner Contest 007 を見てください。