概要

グリッド上にある全ての # タイルを含む最小の長方形を求め、その周の長さを出力する問題です。# が存在しない場合は \(0\) を出力します。

考察

すべての # タイルを含む長方形の周の長さを最小化したいので、長方形をできるだけ小さくする必要があります。

重要な気づき: すべての # を含む最小の長方形は、# が存在する行の最小値・最大値と列の最小値・最大値によって一意に決まります。これはいわゆる バウンディングボックス（bounding box） と呼ばれるものです。

例えば、以下のような \(4 \times 5\) のグリッドを考えます：

.....
.#...
...#.
.....

• # が存在する行: 2行目と3行目 → \(r_1 = 2, r_2 = 3\)
• # が存在する列: 2列目と4列目 → \(c_1 = 2, c_2 = 4\)

この長方形の周の長さは \(2 \times ((3 - 2 + 1) + (4 - 2 + 1)) = 2 \times (2 + 3) = 10\) となります。

これより小さい長方形では、いずれかの # がはみ出してしまうため、この長方形が最小です。

素朴なアプローチとの比較: 全ての \((r_1, r_2, c_1, c_2)\) の組み合わせを試すと \(O(H^2 W^2)\) になりますが、バウンディングボックスは一意に決まるので、全タイルを1回走査するだけで求められます。

アルゴリズム

1. グリッドを1マスずつ走査する。
2. # を見つけるたびに、以下の4つの値を更新する：
   • \(\text{min\_r}\): # が存在する行の最小値
   • \(\text{max\_r}\): # が存在する行の最大値
   • \(\text{min\_c}\): # が存在する列の最小値
   • \(\text{max\_c}\): # が存在する列の最大値
3. 走査終了後、# が1つも存在しなければ \(0\) を出力する。
4. 存在すれば、周の長さ \(2 \times ((\text{max\_r} - \text{min\_r} + 1) + (\text{max\_c} - \text{min\_c} + 1))\) を出力する。

計算量

• 時間計算量: \(O(H \times W)\)（全タイルを1回ずつ走査するだけ）
• 空間計算量: \(O(W)\)（各行の文字列を1行ずつ読み込むだけで済む）

実装のポイント

• 初期値の設定: \(\text{min\_r}\) と \(\text{min\_c}\) は十分大きい値（\(H+1, W+1\)）に、\(\text{max\_r}\) と \(\text{max\_c}\) は \(0\) に初期化しておくことで、最初の # 発見時に正しく更新されます。

• # が存在しない場合の判定: 走査後に \(\text{max\_r} = 0\) のままであれば、# は1つも見つからなかったと判定できます。

• 1-indexed vs 0-indexed: コード中では行・列を1-indexedで管理していますが、差分を取って周の長さを計算するため、0-indexedでも最終結果は同じになります。

  ソースコード

H, W = map(int, input().split())
min_r, max_r, min_c, max_c = H + 1, 0, W + 1, 0
for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == '#':
            if i + 1 < min_r:
                min_r = i + 1
            if i + 1 > max_r:
                max_r = i + 1
            if j + 1 < min_c:
                min_c = j + 1
            if j + 1 > max_c:
                max_c = j + 1
if max_r == 0:
    print(0)
else:
    print(2 * ((max_r - min_r + 1) + (max_c - min_c + 1)))

---

この解説は claude4.6opus-thinking によって生成されました。