Exam Practice

Appearance

Exam05: BSQ (Lv2) ​

障害物（Obstacles）を避けながら、地図上で「最大の正方形（Biggest Square）」を見つけるアルゴリズム課題です。

課題概要 ​

  • 目的: 与えられた地図の中で、最大の正方形を描ける位置を探し、そこを「埋まり文字（Full char）」で埋めて表示する。
  • 優先順位: 複数の解がある場合、最も「上」、それが同じなら最も「左」にあるものを選ぶ。
  • 入力形式: ファイルまたは標準入力。1行目にパラメーター（行数、空文字、障害物、埋まり文字）が与えられる。

主要技術の深掘り ​

動的計画法 (Dynamic Programming) ​

この問題の最も効率的な解法は、動的計画法（DP）を使用することです。 各地点 (i, j) において、「そこを右下角とする最大の正方形のサイズ」を計算し、メモ化します。

漸化式:

c
if (map[i][j] == obstacle) {
    value[i][j] = 0;
} else {
    value[i][j] = min(value[i-1][j], value[i][j-1], value[i-1][j-1]) + 1;
}
  • value[i-1][j]: 上のマス
  • value[i][j-1]: 左のマス
  • value[i-1][j-1]: 左上のマス

これら3つの最小値に1を足したものが、(i, j) で作れる正方形のサイズになります。

ロジックの可視化 ​

DPテーブルの構築プロセス ​

コラム・読み物 ​

アルゴリズムの背景にある理論や、現実世界での応用についての深掘り記事です。

よくある質問 (FAQ) ​

Q. マップが巨大な場合は？ ​

A. マップ全体をメモリに保持する必要がありますが、DPテーブルは必ずしも別の配列として確保する必要はありません。入力の文字配列をそのまま利用する（整数配列に変換するコストと相談）などの工夫が可能です。ただし、試験環境では素直に int** や int* の配列を確保するのが無難です。

Q. 複数のファイルが渡されたら？ ​

A. 各ファイルの処理結果の間に改行を出力するのを忘れないようにしてください。

Q. 改行コードの扱いは？ ​

A. マップの各行は改行 \n で終わっています。バリデーション時に行の長さが一致するか厳密にチェックする必要があります。

参考リンク ​