概要

与えられたグリッドの中で、すべての#（絵画タイル）を含む最小の長方形を見つけて、その周の長さを求める問題です。

考察

この問題では、すべての絵画タイル（#）を囲むことができる最小の長方形を求めたいです。素朴な方法として、「すべての長方形候補を試す」と考えると、行と列の選び方の組み合わせが多くなりすぎて計算時間がかかりすぎてしまいます（TLE）。また、全探索ではなく適当に上下左右の端を決めるだけでも、それが本当に最小の長方形かどうか判断がつきません。

しかし、実はすべての#を含む最小の長方形は、すべての#の位置における行番号の最小値と最大値、列番号の最小値と最大値によって一意に定まります。つまり、最も上にある#、最も下にある#、最も左にある#、最も右にある#を見つければ、それら4つの位置で囲まれる長方形が最小の長方形になります。

例えば以下のような小さなグリッドを考えましょう：

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

この場合、#は(1,1)と(2,2)にあります（0-indexed）。
行の最小・最大：1, 2
列の最小・最大：1, 2
したがって、囲う範囲は行1〜2、列1〜2となり、周の長さは： $\( 2 \times ((2 - 1 + 1) + (2 - 1 + 1)) = 2 \times (2 + 2) = 8 \)$ となります。

このように、#の位置をすべて調べて、その中での最小・最大の行と列を求めることで、効率的に答えを得ることができます。

アルゴリズム

1. グリッド全体を読み込みます。
2. すべての#の位置（行番号と列番号）をリストに記録します。
3. もし#が一つもなければ、答えは \(0\) です。
4. そうでなければ、リスト内の行番号と列番号それぞれについて、最小値と最大値を求めます。
5. これらの値を使って、長方形の高さと幅を計算します。
6. 周の長さ \(2 \times (\text{高さ} + \text{幅})\) を出力します。

計算量

• 時間計算量: \(O(H \times W)\)
  • 各マスを一度だけ確認するため、入力サイズに比例します。
• 空間計算量: \(O(H \times W)\)
  • 最悪の場合、すべてのマスが#になるため、すべての位置を記録する必要があります。

実装のポイント

• #の位置を記録する際に、行と列のインデックスを混同しないように注意しましょう（0-indexed or 1-indexed）。
• 絵画タイルが存在しないケースを忘れずに処理してください。
• 最後に周の長さを正しく計算することを確認しましょう：\(2 \times (\text{縦の長さ} + \text{横の長さ})\)。

## ソースコード

```python
H, W = map(int, input().split())
grid = [input() for _ in range(H)]

# 絵画タイル(#)の位置をすべて取得
paintings = []
for r in range(H):
    for c in range(W):
        if grid[r][c] == '#':
            paintings.append((r, c))

# 絵画タイルが一つもない場合
if not paintings:
    print(0)
else:
    # 行と列の最小・最大を求める
    min_r = min(r for r, c in paintings)
    max_r = max(r for r, c in paintings)
    min_c = min(c for r, c in paintings)
    max_c = max(c for r, c in paintings)

    # 長方形の高さと幅
    height = max_r - min_r + 1
    width = max_c - min_c + 1

    # 周の長さを計算して出力
    perimeter = 2 * (height + width)
    print(perimeter)

この解説は qwen3-coder-480b によって生成されました。