Overview

Find the smallest axis-aligned rectangle (with minimum perimeter) that contains all cells marked with #, and output its perimeter. If there are no # cells, output \(0\).

Approach

To enclose all # cells within a rectangle, we must cover the minimum and maximum rows and minimum and maximum columns where # exists.

• Let \(r_{\min}\) and \(r_{\max}\) be the minimum and maximum rows containing #
• Let \(c_{\min}\) and \(c_{\max}\) be the minimum and maximum columns containing #

Then, any rectangle that contains all # cells must cover at least: - From \(r_{\min}\) to \(r_{\max}\) in the row direction - From \(c_{\min}\) to \(c_{\max}\) in the column direction

Conversely, if we construct a rectangle that exactly covers this range (the so-called “minimum bounding rectangle”), it will certainly contain all # cells, and since the height and width are minimized, the perimeter is also minimized. (The perimeter is \(2 \times (\text{height} + \text{width})\), so smaller height and width are better.)

Naively trying all \((r_1, r_2, c_1, c_2)\) combinations would be \(O(H^2W^2)\), which is far too slow for \(H, W \le 1000\). Instead, it suffices to scan the grid once and collect just the minimum/maximum row and column of #.

Example: If # appears at positions (row, column) = (2,5), (4,3), (3,8), then: - \(r_{\min}=2, r_{\max}=4\), so height is \(4-2+1=3\) - \(c_{\min}=3, c_{\max}=8\), so width is \(8-3+1=6\) The perimeter is \(2(3+6)=18\).

Algorithm

1. Prepare variables min_r, max_r, min_c, max_c to track the minimum/maximum row and column of #.
2. Scan the entire grid once, and whenever # is found:
   • Update min_r = min(min_r, r), max_r = max(max_r, r)
   • Update min_c = min(min_c, c), max_c = max(max_c, c)
3. If no # was found, output \(0\).
4. Otherwise, output:
   • Height \(= max\_r - min\_r + 1\)
   • Width \(= max\_c - min\_c + 1\)
   • Perimeter \(= 2 \times (\text{height} + \text{width})\)

Complexity

• Time complexity: \(O(HW)\) (just one pass over all cells)
• Space complexity: \(O(1)\) (only a constant number of variables to store the min/max values)

Implementation Notes

• In Python, even if rows and columns are 0-indexed, it doesn’t matter since we only compute height/width from differences (just don’t forget the \(+1\) at the end).

• For easy detection of the case where no # exists, initializing max_r to -1 works well (if any # is found, it will be updated to at least \(0\)).

• Since the input can be up to \(1000 \times 1000\), using sys.stdin.readline is safer for performance.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    
    min_r, max_r = H, -1
    min_c, max_c = W, -1
    
    for r in range(H):
        s = input().strip()
        for c, ch in enumerate(s):
            if ch == '#':
                if r < min_r: min_r = r
                if r > max_r: max_r = r
                if c < min_c: min_c = c
                if c > max_c: max_c = c
    
    if max_r == -1:
        print(0)
        return
    
    height = max_r - min_r + 1
    width = max_c - min_c + 1
    print(2 * (height + width))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.