「落ちものシミュレーション」を解くために : part2 ※番兵値

今回は paiza の「「落ちものシミュレーション」を解くために : part2」の問題に挑戦！

問題概要

• 縦 H、横 W のフィールドがある
• フィールドの 上から 1×1 のブロックが N 個、順番に落ちてくる
• 各ブロックには
  • 落ちてくる 列（x） が指定されている
• ブロックは
  • 下に他のブロックがある
  • またはフィールドの底に到達
    した時点で固定される
• 途中経過は出力しない
• すべて落ち終わったあとの最終状態を出力する

入力

• H W N
  • H：フィールドの高さ（行数）
  • W：フィールドの幅（列数）
  • N：落ちてくるブロックの個数
• h_i w_i x_i
  • 今回の問題では
    • h_i = 1
    • w_i = 1
  • 実質的に使うのは
    • x_i（どの列に落ちるか）だけ

出力

• 上から H 行 を出力
• 各行は 長さ W の文字列
• 各マスの表現
  • #：ブロックあり
  • .：空き

入力例:

3 3 3
1 1 1
1 1 2
1 1 1

出力例:

...
.#.
.##

✅OK例：

const readline = require('readline');

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

let lines = [];

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

rl.on('close', () => {
  // 1行目の入力
  let [H, W, N] = lines[0].split(' ').map(Number);

  // フィールドの状態を表す H×W の2次元配列
  let field = Array.from({ length: H }, () => Array(W).fill('.'));

  // N 個のブロックを順に処理
  for (let n = 0; n < N; n++) {
    let [h, w, x] = lines[n + 1].split(' ').map(Number);

    // ブロックの下側の辺が来る行
    let bottom = -1;

    // 上から順に見て、すでにブロックがある場所を探す
    for (let i = 0; i < H; i++) {
      if (field[i][x] === '#') {
        bottom = i - 1;
        break;
      }
    }

    // ブロックを置く
    if (bottom === -1) {
      // フィールドの底辺に接触
      field[H - 1][x] = '#';
    } else {
      // 他のブロックの上に接触
      field[bottom][x] = '#';
    }
  }

  // 結果を出力
  for (let i = 0; i < H; i++) {
    console.log(field[i].join(''));
  }
});

🔍コード流れ

① 入力準備

• readline を使って標準入力を1行ずつ受け取る
• 受け取った各行を lines 配列に順番に保存する

② 入力完了後にメイン処理開始

• すべての入力が終わると rl.on('close', ...) が呼ばれる

③ フィールドの初期化

• 1行目から H（高さ）, W（幅）, N（ブロック数） を取得
• 高さ H、幅 W の 2次元配列 field を作成
• すべてのマスを '.'（空）で初期化

④ ブロックを1つずつ落とす（N回）

• 各行から x（落ちる列）を取得
• bottom = -1 を「まだ置き場所が決まっていない」目印として用意

⑤ 落下位置を探す

• フィールドを 上から下へ 調べる
• すでに '#' があったら
  → その 1つ上の行 にブロックが止まる
  → bottom = i - 1 として探索終了

⑥ ブロックを固定する

• bottom === -1 のまま
  → 下に何もなかったので 一番下の行 に置く
• そうでなければ
  → 見つけたブロックの 直上 に置く

⑦ 結果を出力

• 上の行から順に、2次元配列を文字列にして表示

📝まとめ

• 1列ごとに縦方向へ積み上げるシミュレーション
  • ブロックは横に動かず、指定された列にまっすぐ落ちる
• 毎回確認するのは「真下に何があるか」だけ
  • 既存ブロックがあればその直上に止まる
  • 何もなければフィールドの底に止まる
• ブロックが 1×1 なので処理が単純
  • 衝突判定は 1 マスのみ
  • 複雑な重なりや回転を考える必要がない
• 番兵値（bottom = -1）の使い方がポイント
  • 「まだ置き場所が決まっていない」状態を表す
  • 探索後に
    • -1 のまま → 底に置く
    • 更新されている → その位置に置く
  • 余計なフラグ変数を増やさずに分岐できる