概要

この問題は、グリッド上に配置されたすべての絵画タイル（#）を含む最小の長方形の周の長さを求める問題です。

考察

重要な観察は、すべての絵画タイルを含む最小の長方形は、絵画タイルの存在する行と列の最小値と最大値によって決定されるということです。具体的には： - 最小の行インデックス（min_row） - 最大の行インデックス（max_row） - 最小の列インデックス（min_col） - 最大の列インデックス（max_col）

これらの値から長方形の高さと幅を計算し、周の長さを求めます。素朴なアプローチでは、すべての可能な長方形を試すと計算量が \(O(H^2W^2)\) となり、制約条件（\(H, W \leq 1000\)）では実行時間が非常に長くなってしまいます。しかし、上記の観察により、効率的に解くことができます。

アルゴリズム

1. グリッドを読み込みます。
2. すべてのセルを走査し、絵画タイル（#）が存在するかチェックします。
3. 絵画タイルが見つかった場合、その行インデックスと列インデックスを使って最小値と最大値を更新します。
4. 絵画タイルが1つもない場合は0を出力します。
5. 最小の行と最大の行から高さ（height = max_row - min_row + 1）を、最小の列と最大の列から幅（width = max_col - min_col + 1）を計算します。
6. 周の長さは \(2 \times (height + width)\) で求め、出力します。

計算量

• 時間計算量: \(O(H \times W)\)
  • グリッドを1回走査するため
• 空間計算量: \(O(H \times W)\)
  • グリッドを保存するため

実装のポイント

• 初期値の設定：最小値は可能な最大値（HやW）に、最大値は-1に設定します。

• 絵画タイルが存在しない場合の処理：カウンタを使って絵画タイルの存在をチェックし、ない場合は0を出力します。

• インデックスの扱い：グリッドのインデックスは0から始まるため、行と列の範囲を計算する際に+1する必要があります。

  ソースコード

def main():
    import sys
    data = sys.stdin.read().splitlines()
    if not data:
        print(0)
        return
        
    H, W = map(int, data[0].split())
    grid = []
    for i in range(1, H+1):
        grid.append(data[i].strip())
    
    min_row = H
    max_row = -1
    min_col = W
    max_col = -1
    count = 0
    
    for i in range(H):
        for j in range(W):
            if grid[i][j] == '#':
                count += 1
                if i < min_row:
                    min_row = i
                if i > max_row:
                    max_row = i
                if j < min_col:
                    min_col = j
                if j > max_col:
                    max_col = j
                    
    if count == 0:
        print(0)
        return
        
    height = max_row - min_row + 1
    width = max_col - min_col + 1
    perimeter = 2 * (height + width)
    print(perimeter)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。