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

新たに BFS のアルゴリズムについて学んだ！

🧩 問題概要

🎮 問題の設定

盤面は H×W。
マスには以下の 3 種類がある：
- '*' … プレイヤーの現在の陣地（スタート地点は必ず 1 つ）
- '.' … 何もないマス（進める）
- '#' … 障害物（進めない）

🎯 プレイヤーの操作

プレイヤーの陣地（'*'）から上下左右に 1 マス移動できる。
移動できる '.' マスはすべて '*' に塗り替える。
新しく '*' になったマスからもさらに広がっていく。
'#' は通れない & 塗れない。
もう広がらなくなるまで続ける。

📝 最終的に…

陣地として到達できたマスすべてが '*' になった盤面を出力する。

入力例：

3 3
*.#
..#
##.

出力例：

**#
**#
##.

🔺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(''));
    
    while (true){
        let change = false;
        
        for (let i = 0; i < H; i++) {
            for (let j = 0; j < W; j++) {
                if (gridS[i][j] === '*') {
                    if (i > 0 && gridS[i-1][j] === '.') {
                        gridS[i-1][j] = '*'; 
                        change = true;
                    }
                    if (i < H-1 && gridS[i+1][j] === '.') {
                        gridS[i+1][j] = '*'; 
                        change = true;
                    }
                    if (j > 0 && gridS[i][j-1] === '.') {
                        gridS[i][j-1] = '*'; 
                        change = true;
                    }
                    if (j < W-1 && gridS[i][j+1] === '.') {
                        gridS[i][j+1] = '*'; 
                        change = true;
                    }
                }
                
            }
        }
        
        if (!change) {
            gridS.forEach(s => console.log(s.join('')));
            return;
        }
    }
});

* は、障害物 # を避けつつ上下左右の . に広がる
広がらなくなるまで繰り返す
最終形を出力する

テストケースは一応通過したが、アルゴリズムとしては非効率かつTLEしやすくて危険なので、あまり良くなさそう。

✅ OK例：幅優先探索（BFS）

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

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

    // BFS キュー
    const my_p = [];

    // 最初の * の位置をすべてキューへ
    for (let y = 0; y < H; y++) {
        for (let x = 0; x < W; x++) {
            if (s[y][x] === '*') {
                my_p.push([y, x]);
            }
        }
    }

    // BFS
    while (my_p.length > 0) {
        const [y, x] = my_p.shift(); // pop(0)

        if (y > 0 && s[y - 1][x] === '.') {
            s[y - 1][x] = '*';
            my_p.push([y - 1, x]);
        }
        if (y < H - 1 && s[y + 1][x] === '.') {
            s[y + 1][x] = '*';
            my_p.push([y + 1, x]);
        }
        if (x > 0 && s[y][x - 1] === '.') {
            s[y][x - 1] = '*';
            my_p.push([y, x - 1]);
        }
        if (x < W - 1 && s[y][x + 1] === '.') {
            s[y][x + 1] = '*';
            my_p.push([y, x + 1]);
        }
    }

    // 出力
    for (let y = 0; y < H; y++) {
        console.log(s[y].join(''));
    }
});

🎯 まず BFS（幅優先探索）とは何か？

📢 一言で言うと……
近い場所から順番に探索を広げていく方法。

水がじわ〜っと四方向に広がっていくイメージ。

🌊 BFS の具体例

* がスタートだとすると BFS はこう広がる。

* がある地点をキューに入れる（スタート）
キューから取り出す
上下左右を調べる
到達できる場所（'.'）を新たな * にし、キューに追加する
キューが空になるまで繰り返す

これを続けると、最終的には上下左右に行けるだけ * が広がる。

🗒️ BFSの特徴

✔ 近い順に広がる
キュー（FIFO）を使うことで、「先に入れた場所から順に処理」される。

✔ 無駄な重複探索をしない
一度訪れたところはまたキューに入れない → 効率が良い。

✔ 最短距離探索にも使える
迷路で最短手を求めるとき BFS が使われるのはこのため。

🔍 では、この問題で BFS がどう使われているか？

問題文の要点：

* はプレイヤーの陣地
上下左右に進める限り、すべて陣地（*）に塗り替える
# は障害物なので通れない

つまり、

「プレイヤーの陣地から上下左右に行ける場所をすべて塗りつぶす」
→ これはまさに BFS

💻 ここからコードの解説

① 入力の読み込み

const [H, W] = lines[0].split(' ').map(Number);
const s = lines.slice(1).map(line => line.split(''));

H 行、W 列の盤面を 2 次元配列 s に格納。

② 最初にある * をすべて探してキューに追加

const my_p = [];

for (let y = 0; y < H; y++) {
    for (let x = 0; x < W; x++) {
        if (s[y][x] === '*') {
            my_p.push([y, x]);
        }
    }
}

複数の * があっても OK。
BFS は複数起点でも問題なく同時に広がる。

③ BFS 開始（キューが空になるまで）

while (my_p.length > 0) {
    const [y, x] = my_p.shift();  // 先頭を取り出す

ここで BFS の本体。

※ shift() は Array インスタンスのメソッドで、配列から最初の要素を取り除き、その要素を返す。このメソッドは配列の長さを変える。

周囲4方向を確認する

if (y > 0 && s[y - 1][x] === '.') {
    s[y - 1][x] = '*';
    my_p.push([y - 1, x]);
}

'.' なら進める → * に塗る
新しい陣地も BFS の次の探索対象（だからキューへ push）

下・左・右も同様。

④ BFS 完了後に盤面出力

for (let y = 0; y < H; y++) {
    console.log(s[y].join(''));
}

🗒️ まとめ

🔹 1. この問題は「到達可能なマスを全部塗る」問題

障害物 '#' を除いて
スタート地点 '*' からつながっているすべてのマスを塗りつぶすだけの問題。

→ 広がり方は「上下左右のみ」。

🔹 2. 最適解は BFS（幅優先探索）

理由：

陣地が起点から四方に広がる動作 → まさに BFS 。
一度訪れたマスをもう一度見ない → 効率がいい。
最大でも 20×20 = 400 マス → BFS なら十分高速。

🔹 3. BFS の基本動作

キュー（FIFO）にスタートを入れる
キューから取り出す
上下左右を調べる
行ける場所なら塗って、次の探索対象としてキューへ追加
キューが空になるまで繰り返す

→ これで全ての到達可能地点を確実に探索できる。

🔹 4. なぜ while(true) 全探索ループ法は非推奨か

最初に書いた方法：

全マスを毎回チェック
塗り替えが起きるたびに再スキャン
最大 400 マス × 400 回 = 160,000 回
→ 小さな問題なら動くが、一般的な問題では「TLE」の原因になる

BFS は「必要なところだけ順に処理」できるので格段に効率が良い。

🔹 5. BFS 実装のポイント（JS版）

queue.shift() で先頭を取り出す（FIFO）
塗ったら push() して次の探索点に追加
陣地にできたら '*' に書き換えるので「調査済みフラグ」になる（重複防止）