陣取りのターン数

今回は paiza の「陣取りのターン数」の問題に挑戦！

問題概要

• 盤面（H×W ）が与えられる。
• マスの種類は
  .（空き）, #（障害物）, *（スタート位置／陣地） の3種類。
• * のマスは 1つだけ あり、そこがプレイヤーの開始地点。

🔍 ルール

• プレイヤーの陣地（*）から 上下左右に1マス進める場所 を新しい陣地にする。
• ただし 障害物 # は通れない。
• プレイヤーの開始時の位置からの距離が l_i のマスは 「?」 として塗る。
• それ以外の距離は * として塗る。

📌 目的

最終的に
プレイヤーが行ける場所すべてを * または ? に塗った盤面を出力する。

入力例：

3 3 2
*..
...
...
1
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, N] = lines[0].split(' ').map(Number);
    const gridS = lines.slice(1, H+1).map(line => line.split(''));
    const len = lines.slice(H+1).map(Number);
    
    // 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) + 操作回数カウント
                if (len.includes(0)) 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] === '.') {
            if (!len.includes(nextCount)) gridS[y-1][x] = '*';
            else gridS[y-1][x] = '?';
            
            queue.push([y-1, x, nextCount]);
        }
        if (y < H-1 && gridS[y+1][x] === '.') {
            if (!len.includes(nextCount)) gridS[y+1][x] = '*';
            else gridS[y+1][x] = '?';
            
            queue.push([y+1, x, nextCount]);
        }
        if (x > 0 && gridS[y][x-1] === '.') {
            if (!len.includes(nextCount)) gridS[y][x-1] = '*';
            else gridS[y][x-1] = '?';
            
            queue.push([y, x-1, nextCount]);
        }
        if (x < W-1 && gridS[y][x+1] === '.') {
            if (!len.includes(nextCount)) gridS[y][x+1] = '*';
            else gridS[y][x+1] = '?';
            
            queue.push([y, x+1, nextCount]);
        }
    }
    
    // 結果を出力
    gridS.forEach(s => console.log(s.join('')));
});

🔍 コードの流れ

1. 入力を読み込む
   • H, W, N を取得
   • 盤面 gridS（H 行 × W 列）を読み込む
   • len に '?' にする距離リスト l_i を読み込む
2. 最初の * の位置を探す
   • 全マスを走査して、プレイヤー開始位置（*）を見つける
   • 見つけたら BFS キューに (y, x, 距離0) を入れる
   • もし距離 0 が len に含まれていたら、そのマスを ? に変える
3. BFS を開始する
   • キューが空になるまで以下を繰り返す
4. キューから 1 マス取り出す
   • 現在位置 (y, x) と距離 curCount を取り出す
   • 次の距離 nextCount = curCount + 1
5. 上下左右 4 方向をチェック
   • 盤面の範囲内か確認
   • '.'（まだ未訪問で障害物でない）なら進める
6. そのマスの記号を決定する
   • nextCount が len に含まれている → ?
   • 含まれていない → *
7. そのマスをキューに追加
   • (ny, nx, nextCount) をキューに push
8. すべての BFS が終わったら
   • 最終盤面 gridS をそのまま出力する

※ 前回書いたのコードを引っ張ってきたので変数名が怪しいところがあるかも。

✅OK例２： dy/dx

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

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

rl.on('close', () => {
    const [H, W, N] = lines[0].split(' ').map(Number);
    const grid = lines.slice(1, H + 1).map(line => line.split(''));
    const lens = lines.slice(H + 1).map(Number);  // '?' にする距離リスト

    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 (grid[y][x] === '*') {
                queue.push([y, x, 0]);   // y, x, 距離
                // 距離0が '?' 対象なら置き換える
                if (lens.includes(0)) grid[y][x] = '?';
                break LABEL;
            }
        }
    }

    // BFS
    while (queue.length > 0) {
        const [y, x, dist] = queue.shift();　// dist = 距離 (distance)
        const next = dist + 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 (grid[ny][nx] !== '.') continue;

            // 次の距離が '?' 対象かどうか
            grid[ny][nx] = lens.includes(next) ? '?' : '*';

            queue.push([ny, nx, next]);
        }
    }

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

上下左右の処理を dy/dx 配列で統一し、コードを短縮＆整理。

📝まとめ

🌟 BFS で効率的な処理を目指す。

🌟 未訪問チェック
「 . → まだ訪問していない」
→ '*' や '?' に変えた時点で 訪問済み の扱いになる。

🌟 4方向処理は dy/dx で書いて短縮

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

if 文を4回書くよりミスが減り、読みやすくなる。

🌟 len.includes(dist) で条件分岐

• 距離が指定されたものなら ?
• それ以外は *
  → この問題のポイントは距離で記号を変えること