概要

# が描かれているマスをすべて含むような、最小の（周の長さが最小の）軸に平行な長方形を求め、その周の長さを出力します。# が一つもなければ \(0\) です。

考察

長方形で全ての # を含むためには、# が存在する 行の最小・最大 と 列の最小・最大 を必ず含む必要があります。

• # がある行の最小を \(r_{\min}\)、最大を \(r_{\max}\)
• # がある列の最小を \(c_{\min}\)、最大を \(c_{\max}\)

とすると、どんな長方形でも # を全て含むには少なくとも - 行方向は \(r_{\min}\) から \(r_{\max}\) - 列方向は \(c_{\min}\) から \(c_{\max}\) を覆わなければなりません。

逆に、この範囲をちょうど囲む長方形（いわゆる「外接する最小の長方形」）を作れば、全ての # を確実に含み、かつ高さ・幅が最小になるため周の長さも最小になります。
（周の長さは \(2 \times (\text{高さ} + \text{幅})\) なので、高さ・幅が小さいほど有利。）

素朴に「すべての \((r_1,r_2,c_1,c_2)\) を試す」と \(O(H^2W^2)\) となり、\(H,W \le 1000\) では到底間に合いません。
そこで、グリッドを1回走査して # の最小/最大の行・列だけを集めれば十分です。

例：# の位置が (行,列) で (2,5), (4,3), (3,8) にあるなら
- \(r_{\min}=2, r_{\max}=4\) なので高さは \(4-2+1=3\) - \(c_{\min}=3, c_{\max}=8\) なので幅は \(8-3+1=6\)
周の長さは \(2(3+6)=18\) になります。

アルゴリズム

1. 変数 min_r, max_r, min_c, max_c を用意し、# の行・列の最小/最大を管理する。
2. グリッド全体を1回走査し、# を見つけたら
   • min_r = min(min_r, r), max_r = max(max_r, r)
   • min_c = min(min_c, c), max_c = max(max_c, c) を更新する。
3. 一度も # が見つからなければ \(0\) を出力。
4. そうでなければ
   • 高さ \(= max_r - min_r + 1\)
   • 幅 \(= max_c - min_c + 1\)
   • 周の長さ \(= 2 \times (\text{高さ} + \text{幅})\) を出力する。

計算量

• 時間計算量: \(O(HW)\)（全マスを1回見るだけ）
• 空間計算量: \(O(1)\)（最小/最大を保持する定数個の変数のみ）

実装のポイント

• Pythonでは行・列を \(0\) 始まりで扱っても、差分で高さ/幅を出すだけなので問題ありません（最後に \(+1\) を忘れない）。

• # が存在しないケース判定のため、max_r を初期値 -1 にしておくと簡単です（見つかれば必ず \(0\) 以上に更新される）。

• 入力が最大 \(1000 \times 1000\) なので、sys.stdin.readline を使うと安全です。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    
    min_r, max_r = H, -1
    min_c, max_c = W, -1
    
    for r in range(H):
        s = input().strip()
        for c, ch in enumerate(s):
            if ch == '#':
                if r < min_r: min_r = r
                if r > max_r: max_r = r
                if c < min_c: min_c = c
                if c > max_c: max_c = c
    
    if max_r == -1:
        print(0)
        return
    
    height = max_r - min_r + 1
    width = max_c - min_c + 1
    print(2 * (height + width))

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。