概要

グリッド上の #（宝）があるマスをすべて含む、軸に平行な最小の長方形を求め、その面積（マス数）を計算します。

考察

宝があるマス全体を含む「最小の長方形」を作るには、宝が存在する行・列の範囲（最小行〜最大行、最小列〜最大列）を知れば十分です。

• 例えば、宝があるマスの座標が散らばっていても、
  • 一番上にある宝の行番号 = 長方形の上端
  • 一番下にある宝の行番号 = 長方形の下端
  • 一番左にある宝の列番号 = 長方形の左端
  • 一番右にある宝の列番号 = 長方形の右端
    となり、これより内側に縮めるとどれかの宝がはみ出してしまうため、これが最小です。

素朴に「全ての長方形を列挙して、全部の # を含むか判定する」ような方法は、長方形の数が \(O(N^2M^2)\) もあり、\(N, M \le 1000\) では到底間に合いません（TLEになります）。

そこで、グリッドを1回走査して # の行・列の最小値と最大値だけを更新することで、最小長方形を直接求めます。

アルゴリズム

1. min_r, max_r, min_c, max_c を用意する（宝が見つかった行・列の最小/最大）。
   • 初期値は min_r=N, max_r=-1, min_c=M, max_c=-1 のように「まだ見つかっていない」状態にする。
2. グリッドを上から順に全探索する。
   • マス \((i, j)\) が # なら以下を更新する：
     • min_r = min(min_r, i)
     • max_r = max(max_r, i)
     • min_c = min(min_c, j)
     • max_c = max(max_c, j)
3. 最小長方形の高さは \((max_r - min_r + 1)\)、幅は \((max_c - min_c + 1)\)。
4. 面積は
   $\( (max_r - min_r + 1)\times(max_c - min_c + 1) \)$ を出力する。

※問題文より # は少なくとも1つ存在するため、最終的に必ず範囲が確定します。

計算量

• 時間計算量: \(O(NM)\)（全マスを1回見るだけ）
• 空間計算量: \(O(1)\)（範囲を表す変数だけ。入力文字列は1行ずつ処理）

実装のポイント

• 座標は 0-index（Pythonの for i in range(N) / enumerate）で扱うとそのまま書けます。面積計算では +1 を忘れないことが重要です。

• input().strip() で改行を除いてから文字を走査します。

• # が必ず存在する前提なので、範囲が未更新のままになるケースを特別扱いする必要はありません。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    min_r, max_r = N, -1
    min_c, max_c = M, -1

    for i in range(N):
        s = input().strip()
        for j, ch in enumerate(s):
            if ch == '#':
                if i < min_r: min_r = i
                if i > max_r: max_r = i
                if j < min_c: min_c = j
                if j > max_c: max_c = j

    area = (max_r - min_r + 1) * (max_c - min_c + 1)
    print(area)

if __name__ == "__main__":
    main()

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