Overview

Given a grid, find the smallest rectangle that contains all # (painting tiles) and calculate its perimeter.

Analysis

In this problem, we want to find the smallest rectangle that can enclose all painting tiles (#). A naive approach of “trying all possible rectangle candidates” would result in too many combinations of row and column choices, leading to excessive computation time (TLE). Even if we try to determine the top, bottom, left, and right boundaries without exhaustive search, it would be difficult to verify whether it truly is the smallest rectangle.

However, the smallest rectangle containing all # tiles is actually uniquely determined by the minimum and maximum row numbers and the minimum and maximum column numbers among all # positions. In other words, by finding the topmost #, the bottommost #, the leftmost #, and the rightmost #, the rectangle enclosed by these four positions becomes the smallest rectangle.

For example, consider the following small grid:

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

In this case, # is at positions (1,1) and (2,2) (0-indexed).
Row min/max: 1, 2
Column min/max: 1, 2
Therefore, the enclosing range is rows 1–2, columns 1–2, and the perimeter is: $\( 2 \times ((2 - 1 + 1) + (2 - 1 + 1)) = 2 \times (2 + 2) = 8 \)$

In this way, by examining all # positions and finding the minimum and maximum rows and columns among them, we can efficiently obtain the answer.

Algorithm

1. Read the entire grid.
2. Record the positions (row number and column number) of all # tiles in a list.
3. If there are no # tiles, the answer is \(0\).
4. Otherwise, find the minimum and maximum values for both row numbers and column numbers in the list.
5. Using these values, calculate the height and width of the rectangle.
6. Output the perimeter \(2 \times (\text{height} + \text{width})\).

Complexity

• Time complexity: \(O(H \times W)\)
  • Since each cell is checked exactly once, it is proportional to the input size.
• Space complexity: \(O(H \times W)\)
  • In the worst case, all cells are #, so all positions need to be recorded.

Implementation Notes

• Be careful not to confuse row and column indices when recording # positions (0-indexed or 1-indexed).
• Don’t forget to handle the case where no painting tiles exist.
• Make sure the perimeter is calculated correctly: \(2 \times (\text{vertical length} + \text{horizontal length})\).

## Source Code

```python
H, W = map(int, input().split())
grid = [input() for _ in range(H)]

# 絵画タイル(#)の位置をすべて取得
paintings = []
for r in range(H):
    for c in range(W):
        if grid[r][c] == '#':
            paintings.append((r, c))

# 絵画タイルが一つもない場合
if not paintings:
    print(0)
else:
    # 行と列の最小・最大を求める
    min_r = min(r for r, c in paintings)
    max_r = max(r for r, c in paintings)
    min_c = min(c for r, c in paintings)
    max_c = max(c for r, c in paintings)

    # 長方形の高さと幅
    height = max_r - min_r + 1
    width = max_c - min_c + 1

    # 周の長さを計算して出力
    perimeter = 2 * (height + width)
    print(perimeter)

---

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