Overview

This is a problem to find the area of the minimum rectangle that contains all cells with # (treasure) on a grid.

Analysis

Key Insight

To find the minimum rectangular region, it is sufficient to know just the “topmost”, “bottommost”, “leftmost”, and “rightmost” positions of cells containing treasure.

For example, consider the following map:

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

In this case: - The topmost # is at row 2 (index 1) - The bottommost # is at row 3 (index 2) - The leftmost # is at column 2 (index 1) - The rightmost # is at column 4 (index 3)

Therefore, the minimum rectangle has height \(2 - 1 + 1 = 2\) cells and width \(3 - 1 + 1 = 3\) cells, giving an area of \(2 \times 3 = 6\).

Why This Works

Any rectangle containing all treasures must satisfy the following: - Top edge ≤ all treasure row numbers - Bottom edge ≥ all treasure row numbers - Left edge ≤ all treasure column numbers - Right edge ≥ all treasure column numbers

To minimize the area, we should maximize the top and left edges, and minimize the bottom and right edges. Therefore, the optimal solution is to match them with the minimum and maximum values of the treasure positions respectively.

Algorithm

1. Initialize variables

   • min_row, min_col: minimum row and column of treasures (initialize with large values)
   • max_row, max_col: maximum row and column of treasures (initialize with small values)

2. Scan all cells of the grid

   • If a cell is # (treasure), update the four variables using that cell’s position \((i, j)\)

3. Calculate the height and width of the rectangle

   • Height = max_row - min_row + 1
   • Width = max_col - min_col + 1

4. Output the area (height × width)

Complexity

• Time complexity: \(O(N \times M)\)
  • Because we scan each cell of the grid exactly once
• Space complexity: \(O(M)\)
  • We use \(O(M)\) space to read each row’s string
  • There is no need to store the entire grid

Implementation Notes

1. Setting initial values: Initialize min_row and min_col with sufficiently large values (\(N\) or \(M\)), and max_row and max_col with sufficiently small values (such as \(-1\)). This ensures proper updates when the first # is found.

2. Don’t forget the +1: The length of a rectangle’s side is “maximum - minimum + 1”. For example, if row numbers range from 2 to 4, the number of rows included is \(4 - 2 + 1 = 3\) rows.

3. Don’t store the entire grid: By processing each row immediately after reading it, you can save memory.

   Source Code

N, M = map(int, input().split())

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

for i in range(N):
    S = input()
    for j in range(M):
        if S[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)

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

---

This editorial was generated by claude4.5opus.