概要

与えられたグリッド上のすべての宝（#）を囲む最小の長方形領域の面積を求めます。

考察

この問題では、すべての宝を囲むことができる最小の長方形を見つける必要があります。
そのためには、すべての宝のあるマスのうち、「最も上」「最も下」「最も左」「最も右」にあるものの位置を調べればよいです。

たとえば以下のようなグリッドを考えます：

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

この場合、# はそれぞれ \((1,1)\) と \((2,2)\) にあります（0-indexed）。
この2つのマスを囲む最小の長方形は、左上 \((1,1)\)、右下 \((2,2)\) の長方形であり、面積は \(2 \times 2 = 4\) になります。

このように、すべての宝を囲む最小長方形は、含まれるマスの行番号の最小・最大、列番号の最小・最大によって定まります。

素朴な方法として、「すべての宝の座標をリストに保存して、最後に最大最小を調べる」という方法も考えられますが、これでも十分高速です。しかし、無駄なリストの管理をせずに、全マスを見ながら必要な最小・最大値を更新していくのが効率的です。

アルゴリズム

1. 入力を読み込み、地図の状態を保持します。
2. 最小・最大の行番号（min_row, max_row）、最小・最大の列番号（min_col, max_col）を初期化します。
3. 各マスを順に走査し、# であれば現在の最小・最大値を更新します。
4. 最後に、長方形の縦幅：\((max_row - min_row + 1)\)、横幅：\((max_col - min_col + 1)\) を求め、面積を計算して出力します。

計算量

• 時間計算量: \(O(N \times M)\)
• 空間計算量: \(O(N \times M)\) （入力の地図を保持するため）

実装のポイント

• 初期値の設定に注意しましょう：

  • min_row は N、min_col は M といった「ありえない大きな値」にしておくと、最初の # で必ず更新されます。
  • max_row と max_col は -1 などの負の値にしておくと安全です。

• 座標系は0-indexedで統一されていることに注意してください。

  ソースコード

N, M = map(int, input().split())
S = [input() for _ in range(N)]

min_row = N
max_row = -1
min_col = M
max_col = -1

for i in range(N):
    for j in range(M):
        if S[i][j] == '#':
            min_row = min(min_row, i)
            max_row = max(max_row, i)
            min_col = min(min_col, j)
            max_col = max(max_col, j)

area = (max_row - min_row + 1) * (max_col - min_col + 1)
print(area)

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