概要

\(N \times M\) のグリッド状の地図において、宝（#）が埋まっているすべてのマスを囲む最小の長方形領域を特定し、その面積（マスの数）を求める問題です。

考察

「すべての宝を含む最小の長方形」を求めるためには、宝が存在するマスの位置（行番号と列番号）の「端」を特定する必要があります。

具体的には、以下の4つの値を求めることで長方形の範囲が定まります。 - 最小の行番号 (\(min\_r\)): 最も上にある宝の行 - 最大の行番号 (\(max\_r\)): 最も下にある宝の行 - 最小の列番号 (\(min\_c\)): 最も左にある宝の列 - 最大の列番号 (\(max\_c\)): 最も右にある宝の列

これらの値が分かれば、長方形の高さは \(max\_r - min\_r + 1\)、幅は \(max\_c - min\_c + 1\) となり、面積はその積で計算できます。

制約は \(N, M \leq 1000\) であり、全マス数は最大 \(1,000,000\) 個です。すべてのマスを一度ずつ確認する計算量であれば、制限時間内に十分に間に合います。

アルゴリズム

1. 境界となる変数 min_r, max_r, min_c, max_c を初期化します。
   • min_r と min_c は十分大きな値（\(N\) や \(M\) など）で初期化します。
   • max_r と max_c は十分小さな値（\(-1\) など）で初期化します。
2. グリッドの各行を順番に走査します。
3. 各行において、# が含まれているかを確認します。
   • Python の row.find('#') を使うと、その行で最も左にある宝の列番号が取得できます。
   • row.rfind('#') を使うと、その行で最も右にある宝の列番号が取得できます。
4. 宝が見つかった場合、その行番号と列番号を用いて、4つの境界変数を更新します。
5. 全行の走査が終わった後、(max_r - min_r + 1) * (max_c - min_c + 1) を計算して出力します。

計算量

• 時間計算量: \(O(N \times M)\) グリッドの各マスを走査するため、マス数に比例した時間がかかります。\(10^6\) 程度の操作なので高速に動作します。
• 空間計算量: \(O(N \times M)\) 入力されたグリッドの情報をメモリに保持するために必要です。

実装のポイント

• 境界の更新: 各行をループで回す際、その行に一つでも # があれば min_r と max_r の候補になります。特に行番号については、最初に見つかった宝の行が min_r、最後に見つかった宝の行が max_r になるため、効率的に更新できます。

• 効率的な検索: Python の文字列メソッド find や rfind は内部的に高速に動作するため、各マスを個別にループでチェックするよりも実行時間を短縮できる場合があります。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白文字（改行を含む）で分割します。
    # これにより、N, M およびグリッドの各行をリストとして取得できます。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N（行数）と M（列数）を取得
    n = int(input_data[0])
    m = int(input_data[1])
    
    # グリッドの各行を取得
    grid = input_data[2:]
    
    # 宝（'#'）が含まれる最小の長方形領域の境界を初期化
    # min_r: 最小の行インデックス, max_r: 最大の行インデックス
    # min_c: 最小の列インデックス, max_c: 最大の列インデックス
    min_r, max_r = n, -1
    min_c, max_c = m, -1
    
    # 各行を走査して宝の位置を確認する
    for r in range(n):
        row = grid[r]
        # その行で最初に出現する '#' のインデックスを取得
        first_idx = row.find('#')
        
        # '#' がその行に存在する場合
        if first_idx != -1:
            # 行の境界を更新
            if r < min_r:
                min_r = r
            if r > max_r:
                max_r = r
            
            # 列の境界を更新
            # その行で最後に出現する '#' のインデックスを取得
            last_idx = row.rfind('#')
            if first_idx < min_c:
                min_c = first_idx
            if last_idx > max_c:
                max_c = last_idx
    
    # 最小の長方形領域の高さと幅を計算
    height = max_r - min_r + 1
    width = max_c - min_c + 1
    
    # 面積（マスの数）を出力
    print(height * width)

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-preview によって生成されました。