paiza マートの出店計画

今回は paiza の「paiza マートの出店計画」の問題に挑戦！

問題概要

目的

• 町の地図上で、すべての競合店（*）からの最短距離が D 以上となる 空地（.）の個数を求める。

地図のルール

• 地図サイズ：
  • 高さ H、幅 W
• 各マスの意味：
  • .：空地（出店候補）
  • *：競合店（通行不可）
  • #：壁（通行不可）

距離の定義

• 上下左右に 1 マス移動 = 距離 1
  • 斜め移動は不可
  • 「距離」は 最短距離

出店可能条件

• ある空地マスについて：
  • どの競合店から見ても
  • 最短距離が D 以上
• 1つでも D 未満 の競合店があれば 出店不可

制約条件

• H, W ≤ 10000（最大 1億マス級）
• * の数は 最大 100 個

入力例:

6 6 3
..#...
.#....
*...*.
*.#...
#.##.*
......

出力例:

8

✅OK例：

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

const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
  // H: 高さ, W: 幅, D: 最低距離
  const [H, W, D] = lines[0].split(' ').map(Number);
  // 地図情報
  const M = lines.slice(1, H + 1).map(l => l.split(''));

  // 距離配列（-1 = まだどの * からも到達していない）
  const dist = Array.from({ length: H }, () => Array(W).fill(-1));

  // BFS用キュー（shiftを使わず、indexで管理）
  const queue = [];
  let head = 0;

  // 上下左右の移動
  const dir = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1]
  ];

  // すべての競合店(*)を距離0の始点としてキューに入れる
  for (let y = 0; y < H; y++) {
    for (let x = 0; x < W; x++) {
      if (M[y][x] === '*') {
        dist[y][x] = 0;
        queue.push([y, x]);
      }
    }
  }

  // 幅優先探索（距離 D 未満の範囲だけ広げる）
  while (head < queue.length) {
    const [y, x] = queue[head++];
    const d = dist[y][x]; // 競合店(*)からこのマスに到達するまでの移動回数（最短）

    // D 以上になる先は探索しなくてよい
    if (d + 1 >= D) continue;

    for (const [dy, dx] of dir) {
      const ny = y + dy;
      const nx = x + dx;

      // 範囲外チェック
      if (ny < 0 || ny >= H || nx < 0 || nx >= W) continue;
      // 通行不可マス
      if (M[ny][nx] === '#') continue;
      // すでに最短距離が確定しているマス
      if (dist[ny][nx] !== -1) continue;

      // 距離を更新してキューに追加
      dist[ny][nx] = d + 1;
      queue.push([ny, nx]);
    }
  }

  // 出店可能な空地('.')を数える
  let ans = 0;
  for (let y = 0; y < H; y++) {
    for (let x = 0; x < W; x++) {
      // どの * からも D 未満で到達していない空地マス
      if (M[y][x] === '.' && (dist[y][x] === -1 || dist[y][x] >= D)) {
        ans++;
      }
    }
  }

  console.log(ans);
});

🔍コードの流れ

① 入力を受け取る

• H, W, D を読み取る
  → マップの 高さ・幅・最低距離
• マップ M を2次元配列として保持
  • .：空地
  • *：競合店
  • #：壁（通れない）

② 距離管理用の配列を用意

• dist[y][x]
  • -1：まだ どの競合店(*)からも到達していない
  • 0 以上：最寄りの * からの 最短距離

③ BFSの準備

• キュー queue を用意
  • 上下左右の移動方向を定義

④ BFSの始点をセット

• マップ全体を走査
• * を見つけたら
  • dist = 0 にする
  • BFSキューに追加

👉 複数の * から同時に広げる多点スタートBFS

⑤ BFSで距離を広げる

• キューから順に取り出す
• 今いるマスの距離を d とする
• d + 1 >= D なら
  • それ以上は不要なので探索しない
• 上下左右に移動して
  • 範囲外・壁・既訪問はスキップ
  • 初めて到達するマスなら
    • 距離を d + 1 に更新
    • キューに追加

👉 「競合店から距離 D 未満の範囲」だけが埋まる

⑥ 出店可能なマスを数える

• マップ全体を再度チェック
• 条件：
  • マスが .（空地）
  • かつ
    • dist === -1（どの * からも届いていない）
      または
    • dist >= D（競合店から十分遠い）
• 条件を満たすマスをカウント

⑦ 結果を出力

• 出店可能な空地の数を console.log

📝まとめ

〇 距離配列（dist）の役割

• 各マスについて
• 「最寄りの競合店 * からの最短距離」を記録する
• dist[y][x] = -1
  • まだどの * からも到達していない（距離不明）
• dist[y][x] >= 0
  • その距離で最短到達が確定している

👉距離の管理と「訪問済み判定」を同時に行える

〇 BFSを使う理由

• BFSは
  • 移動回数＝距離
  • 最初に到達した時点で最短距離が確定
• グリッドの上下左右移動と相性が良い

〇 多点スタートBFSの意図

• すべての * を
  • 距離0の始点として同時にキューへ入れる
• BFSを1回回すだけで
  • 「最寄りの競合店までの距離」が全マスで求まる

👉「どの * に一番近いか」を個別に考えなくていい

〇 距離 D で探索を打ち切る理由

• 出店可否に必要なのは
  • 距離が D 未満かどうかだけ
• d + 1 >= D になったら
  • それ以上広げても結果に影響しない

👉無駄な探索をしない

〇 最終判定の考え方

• 空地 . のうち
  • dist === -1（どの * からも届かない）
  • または dist >= D（十分遠い）

👉これらだけが出店可能

〇 一文でまとめると

「競合店からBFSで 距離D未満 を塗りつぶし、塗られなかった空地を数える。」