Overview

Find the minimum axis-aligned rectangle on the grid that contains all cells with # (treasure), and calculate its area (number of cells).

Approach

To create the “minimum rectangle” that contains all cells with treasure, it is sufficient to know the range of rows and columns where treasure exists (minimum row to maximum row, minimum column to maximum column).

• For example, even if the coordinates of treasure cells are scattered:
  • Row number of the topmost treasure = top edge of the rectangle
  • Row number of the bottommost treasure = bottom edge of the rectangle
  • Column number of the leftmost treasure = left edge of the rectangle
  • Column number of the rightmost treasure = right edge of the rectangle

Shrinking the rectangle any further inward would cause some treasure to fall outside, so this is the minimum.

A naive approach like “enumerate all rectangles and check whether each contains all # cells” would involve \(O(N^2M^2)\) rectangles, which is far too slow for \(N, M \le 1000\) (it would result in TLE).

Instead, we scan the grid once and only update the minimum and maximum values of the rows and columns of # cells, directly determining the minimum rectangle.

Algorithm

1. Prepare min_r, max_r, min_c, max_c (minimum/maximum of rows and columns where treasure is found).
   • Initialize them to a “not yet found” state, such as min_r=N, max_r=-1, min_c=M, max_c=-1.
2. Scan the entire grid from top to bottom.
   • If cell \((i, j)\) is #, update the following:
     • 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. The height of the minimum rectangle is \((max\_r - min\_r + 1)\), and the width is \((max\_c - min\_c + 1)\).
4. Output the area: $\( (max\_r - min\_r + 1)\times(max\_c - min\_c + 1) \)$

*Note: According to the problem statement, at least one # exists, so the range is guaranteed to be determined in the end.

Complexity

• Time complexity: \(O(NM)\) (just a single pass over all cells)
• Space complexity: \(O(1)\) (only variables representing the range; input strings are processed one line at a time)

Implementation Notes

• Using 0-indexed coordinates (Python’s for i in range(N) / enumerate) allows straightforward implementation. It is important not to forget the +1 in the area calculation.

• Use input().strip() to remove the newline before scanning characters.

• Since # is guaranteed to exist, there is no need to handle the case where the range remains uninitialized.

  Source Code

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

This editorial was generated by gpt-5.2-high.