概要

グリッド上に配置されたすべての絵画タイル（#）を囲む最小の長方形（境界ボックス）を求め、その周の長さを計算する問題です。

考察

すべての絵画タイルを囲むためには、以下の 4 つの値を特定する必要があります。

1. 一番上にある絵画タイルの行番号 (\(r_{min}\))
2. 一番下にある絵画タイルの行番号 (\(r_{max}\))
3. 一番左にある絵画タイルの列番号 (\(c_{min}\))
4. 一番右にある絵画タイルの列番号 (\(c_{max}\))

これらの値が決まれば、すべての絵画タイルを囲む最小の長方形は、行の範囲が \(r_{min}\) から \(r_{max}\)、列の範囲が \(c_{min}\) から \(c_{max}\) となります。

この長方形の高さは \(r_{max} - r_{min} + 1\)、幅は \(c_{max} - c_{min} + 1\) と表せます。 問題文にある通り、周の長さは \(2 \times (\text{高さ} + \text{幅})\) で計算できます。

絵画タイルが 1 つも存在しない場合は、囲むべき対象がないため、問題の指示通り \(0\) を出力します。

アルゴリズム

1. 絵画タイルの位置の最小・最大値を管理する変数 \(r_{min}, r_{max}, c_{min}, c_{max}\) を初期化します。
2. グリッドの各マス \((r, c)\) を順番に確認します。
3. もしマス \((r, c)\) が絵画タイル（#）であれば：
   • \(r_{min}\) を \(r\) との最小値で更新する
   • \(r_{max}\) を \(r\) との最大値で更新する
   • \(c_{min}\) を \(c\) との最小値で更新する
   • \(c_{max}\) を \(c\) との最大値で更新する
   • 「絵画タイルが見つかった」というフラグを立てる
4. 全マスを確認した後、フラグが立っていなければ 0 を出力します。
5. フラグが立っていれば、求めた最小・最大値から周の長さを計算して出力します。

計算量

• 時間計算量: \(O(H \times W)\)
  • グリッドのすべてのマスを 1 回ずつ走査するため、マス目の総数に比例した時間がかかります。\(H, W \leq 1000\) なので、最大 \(10^6\) 回程度の処理となり、十分高速に動作します。
• 空間計算量: \(O(H \times W)\)
  • 入力されたグリッドの情報を保持するために、マス目の総数に比例したメモリを使用します。

実装のポイント

• 効率的な探索: 各行について find('#')（左端）と rfind('#')（右端）を使うことで、すべての文字を個別にチェックするよりも効率的に列の範囲を特定できます。

• 初期値の設定: \(r_{min}\) や \(c_{min}\) には十分大きな値を、\(r_{max}\) や \(c_{max}\) には十分小さな値（または \(-1\) など）を設定しておくと、最初のタイルを見つけたときの更新がスムーズになります。

• 例外処理: 絵画タイルが一つも存在しないケースを if not found: のように判定して、正しく \(0\) を出力するようにします。

  ソースコード

import sys

def solve():
    # Read all input data from standard input and split by whitespace
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
        
    if not input_data:
        return
    
    # H (number of rows) and W (number of columns) are the first two values
    try:
        H = int(input_data[0])
        W = int(input_data[1])
    except (ValueError, IndexError):
        return
    
    # The grid characters start from index 2 in input_data.
    # We join all parts to handle cases where rows might be split by whitespace.
    # This creates a single string containing all '#' and '.' characters in order.
    all_chars = "".join(input_data[2:])
    
    # Initialize the bounding box boundaries for '#' characters
    # r_min, r_max for row indices; c_min, c_max for column indices
    r_min, r_max = H, -1
    c_min, c_max = W, -1
    found = False
    
    # Iterate through the grid row by row
    for r in range(H):
        # Extract the r-th row from the combined string
        # Each row is expected to have exactly W characters.
        row = all_chars[r * W : (r + 1) * W]
        
        # Find the first and last occurrence of '#' in the current row
        first_idx = row.find('#')
        if first_idx != -1:
            found = True
            last_idx = row.rfind('#')
            
            # Update the global bounding box coordinates
            if r < r_min:
                r_min = r
            if r > r_max:
                r_max = r
            if first_idx < c_min:
                c_min = first_idx
            if last_idx > c_max:
                c_max = last_idx
    
    if not found:
        # If no painting tile '#' was found, the perimeter is 0
        print(0)
    else:
        # The number of rows and columns covered by the bounding box
        # height = r2 - r1 + 1, width = c2 - c1 + 1
        height = r_max - r_min + 1
        width = c_max - c_min + 1
        
        # The perimeter is 2 * (height + width)
        # This matches the formula: 2 * ((r2 - r1 + 1) + (c2 - c1 + 1))
        print(2 * (height + width))

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。