Overview

Given an \(N \times M\) grid map, the problem asks you to identify the smallest rectangular region that encloses all cells containing treasure (#), and find its area (number of cells).

Approach

To find the “smallest rectangle containing all treasures,” we need to identify the “extremes” of the positions (row numbers and column numbers) of the cells where treasure exists.

Specifically, the range of the rectangle is determined by finding the following four values: - Minimum row number (\(min\_r\)): The row of the topmost treasure - Maximum row number (\(max\_r\)): The row of the bottommost treasure - Minimum column number (\(min\_c\)): The column of the leftmost treasure - Maximum column number (\(max\_c\)): The column of the rightmost treasure

Once these values are known, the height of the rectangle is \(max\_r - min\_r + 1\), the width is \(max\_c - min\_c + 1\), and the area is their product.

The constraints are \(N, M \leq 1000\), so the total number of cells is at most \(1,000,000\). A solution that checks each cell once is well within the time limit.

Algorithm

1. Initialize the boundary variables min_r, max_r, min_c, max_c.
   • Initialize min_r and min_c to a sufficiently large value (such as \(N\) or \(M\)).
   • Initialize max_r and max_c to a sufficiently small value (such as \(-1\)).
2. Scan each row of the grid in order.
3. For each row, check whether it contains #.
   • Using Python’s row.find('#'), you can obtain the column number of the leftmost treasure in that row.
   • Using row.rfind('#'), you can obtain the column number of the rightmost treasure in that row.
4. If treasure is found, update the four boundary variables using the row number and column numbers.
5. After scanning all rows, compute and output (max_r - min_r + 1) * (max_c - min_c + 1).

Complexity

• Time complexity: \(O(N \times M)\) Since we scan each cell of the grid, the time is proportional to the number of cells. With approximately \(10^6\) operations, this runs efficiently.
• Space complexity: \(O(N \times M)\) This is needed to store the input grid information in memory.

Implementation Notes

• Updating boundaries: When looping through each row, if the row contains at least one #, it becomes a candidate for updating min_r and max_r. In particular, for row numbers, the row of the first treasure found becomes min_r and the row of the last treasure found becomes max_r, allowing efficient updates.

• Efficient searching: Python’s string methods find and rfind operate efficiently internally, so they can reduce execution time compared to checking each cell individually in a loop.

  Source Code

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()

This editorial was generated by gemini-3-flash-preview.