Overview

Find the area of the smallest rectangular region that encloses all treasures (#) on a given grid.

Discussion

In this problem, we need to find the smallest rectangle that can enclose all treasures. To do this, we simply need to find the positions of the “topmost,” “bottommost,” “leftmost,” and “rightmost” cells among all cells containing treasure.

For example, consider the following grid:

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

In this case, the # marks are at \((1,1)\) and \((2,2)\) (0-indexed). The smallest rectangle enclosing these two cells has its top-left at \((1,1)\) and bottom-right at \((2,2)\), giving an area of \(2 \times 2 = 4\).

In this way, the smallest rectangle enclosing all treasures is determined by the minimum and maximum row numbers and the minimum and maximum column numbers of the included cells.

A straightforward approach would be to “store all treasure coordinates in a list and then find the minimum and maximum at the end,” which is fast enough. However, it is more efficient to update the necessary minimum and maximum values while scanning all cells, without managing an unnecessary list.

Algorithm

1. Read the input and store the state of the map.
2. Initialize the minimum and maximum row numbers (min_row, max_row) and the minimum and maximum column numbers (min_col, max_col).
3. Scan each cell in order, and if it is #, update the current minimum and maximum values.
4. Finally, compute the height of the rectangle: \((max\_row - min\_row + 1)\), the width: \((max\_col - min\_col + 1)\), calculate the area, and output it.

Complexity

• Time complexity: \(O(N \times M)\)
• Space complexity: \(O(N \times M)\) (to store the input map)

Implementation Notes

• Be careful with initial value settings:

  • Setting min_row to N and min_col to M (impossibly large values) ensures they will be updated upon encountering the first #.
  • Setting max_row and max_col to -1 or other negative values is safe.

• Note that the coordinate system is consistently 0-indexed.

  Source Code

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)

This editorial was generated by qwen3-coder-480b.