陣取りの手間 (BFS)

今回は paiza の「陣取りの手間」の問題に挑戦！

前回 学んだ「BFS」を使って解いていく！

📘 問題概要

• 盤面は H×W のマップ。
  • '*' が現在プレイヤーのいるマス（陣地）。
  • '.' は移動できる空きマス。
  • '#' は障害物で移動できない。
• プレイヤーは現在の陣地から上下左右に移動できる範囲をすべて陣地にする。
• 到達したマスに「到達までの操作回数」を数字で記録する。
• 最初の '*' の位置は操作回数 0 とする。
• 最終的に、各マスを「操作回数」に置き換えたマップを出力する

入力例:

3 3
*..
...
...

出力例:

012
123
234

✅OK例：

const rl = require('readline').createInterface({ input :process.stdin });

const lines = [];

rl.on('line', (input) => lines.push(input));

rl.on('close', () => {
    const [H, W] = lines[0].split(' ').map(Number);
    const gridS = lines.slice(1).map(line => line.split(''));
    
    // BFS キュー
    const queue = [];
    
    // 最初の * の位置をキューへ
    LABEL:for (let y = 0; y < H; y++) {
        for (let x = 0; x < W; x++) {
            if (gridS[y][x] === '*') {
                queue.push([y, x, 0]); // 座標(y, x) + 操作回数
                gridS[y][x] = 0;
                break LABEL;
            }
        }
    }
    
    // BFS
    while (queue.length > 0) {
        const [y, x, curCount] = queue.shift();
        const nextCount = curCount + 1;
        
        if (y > 0 && gridS[y-1][x] === '.') {
            gridS[y-1][x] = nextCount;
            queue.push([y-1, x, nextCount]);
        }
        if (y < H-1 && gridS[y+1][x] === '.') {
            gridS[y+1][x] = nextCount;
            queue.push([y+1, x, nextCount]);
        }
        if (x > 0 && gridS[y][x-1] === '.') {
            gridS[y][x-1] = nextCount;
            queue.push([y, x-1, nextCount]);
        }
        if (x < W-1 && gridS[y][x+1] === '.') {
            gridS[y][x+1] = nextCount;
            queue.push([y, x+1, nextCount]);
        }
    }
    
    // 結果を出力
    gridS.forEach(s => console.log(s.join('')));
})

🔍 このコードの流れ

1. 入力を読み込む
   • H, W を読む
   • 盤面 gridS を 2 次元配列として読み込む
2. BFS 用のキュー（queue）を作る → BFS（幅優先探索）に使う待ち行列
3. 盤面からスタート地点 * を探す
   • 見つけたら queue に (y, x, 0) を入れる
     → 座標 と 最初の「操作回数 0」（初期値）をセットで入れる。
   • そのマスを gridS[y][x] = 0 に置き換える
     → 数字にして「チェック済みマス」として扱う
   • break LABEL で探索を即終了（1 つしか無いので）
4. BFS 開始
   • queue から先頭を取り出す（[y, x, curCount]）
   • 操作回数： nextCount = curCount + 1 を作る
5. 上下左右の 4 マスをチェック
   • 盤面内か？
   • '.' で未チェックか？
     → これらを満たすなら：
     ・そのマスを nextCount に更新
     ・queue にそのマスを追加
6. queue が空になるまで BFS を繰り返す
7. 完成した盤面を出力
   • gridS を行ごとに console.log(s.join(''))

✨改善版：

const rl = require('readline').createInterface({ input: process.stdin });
const lines = [];

rl.on('line', (input) => lines.push(input));

rl.on('close', () => {
    const [H, W] = lines[0].split(' ').map(Number);
    const gridS = lines.slice(1).map(line => line.split(''));

    const queue = [];
    const dy = [-1, 1, 0, 0];
    const dx = [0, 0, -1, 1];

    // スタート地点（*）を探す
    LABEL:
    for (let y = 0; y < H; y++) {
        for (let x = 0; x < W; x++) {
            if (gridS[y][x] === '*') {
                queue.push([y, x, 0]);      // y, x, 操作回数
                gridS[y][x] = 0;           // 操作回数0で上書き
                break LABEL;
            }
        }
    }

    // BFS開始
    while (queue.length > 0) {
        const [y, x, curCount] = queue.shift();
        const nextCount = curCount + 1;

        for (let i = 0; i < 4; i++) {
            const ny = y + dy[i];
            const nx = x + dx[i];

            // 範囲外は除外
            if (ny < 0 || ny >= H || nx < 0 || nx >= W) continue;

            // '.' にだけ移動できる（未到達）
            if (gridS[ny][nx] !== '.') continue;

            // 操作回数を記録
            gridS[ny][nx] = nextCount;

            // 次の探索へ
            queue.push([ny, nx, nextCount]);
        }
    }

    // 出力
    gridS.forEach(row => console.log(row.join('')));
});

💡改善ポイント

• 移動方向を dy, dx 配列にまとめて管理。

• 上下左右の処理をループ1つで書けるため、コードが短くなる。

• if 文を4回書く必要がなくなり、ミスが減る。

• 拡張（斜め追加など）にも強く、保守性が高い。

📝まとめ

• BFS（幅優先探索）は「近い順に探索する」ので、この問題に最適。
• キュー に「座標＋距離」を入れて管理すると処理がわかりやすくなる。
• 到達したマスを数字に置き換えることで「チェック済み管理」を同時にできる。
• 上下左右の移動は dy/dx 配列でまとめると if を4つ書かずに済む。
• dy/dx を使うと処理が 1 ループでまとまり、可読性も拡張性も高くなる。

僕の失敗談(´;ω;｀)と解決法🐈