【競技プログラミング】AtCoder Beginner Contest 337_D問題

問題

解法手順

1. 入力を受け取る

   • H, W, K を入力から取得
   • H行のグリッド情報を文字列のリストとして取得

2. 変数の初期化

   • 答えを格納する変数 ans を非常に大きな値（INF）で初期化
   • 累積和を記録するための配列 X と D を用意（サイズは max(H, W) + 1）

3. 横方向の探索

   • 各行について以下の処理を行う：
     a. X と D の累積和を計算
     b. 連続する K 個のマスについて、'x' がないかチェック
     c. 'x' がない場合、その区間の '.' の数を数え、ans を更新

4. 縦方向の探索

   • 各列について以下の処理を行う：
     a. X と D の累積和を計算
     b. 連続する K 個のマスについて、'x' がないかチェック
     c. 'x' がない場合、その区間の '.' の数を数え、ans を更新

5. 結果の出力

   • ans が更新されていれば（INFでなければ）その値を出力
   • ans が更新されていなければ（INFのままなら）-1 を出力

ACコード

ac.py

# 1. 入力を受け取る
H, W, K = map(int, input().split())
grid = [input() for _ in range(H)]

# 2. 変数の初期化
INF = float('inf')
ans = INF
X = [0] * (max(H, W) + 1)
D = [0] * (max(H, W) + 1)

# 3. 横方向の探索
for row in grid:
    # a. X と D の累積和を計算
    for i in range(W):
        X[i+1] = X[i] + (row[i] == 'x')
        D[i+1] = D[i] + (row[i] == '.')
    
    # b. 連続する K 個のマスについて、'x' がないかチェック
    # c. 'x' がない場合、その区間の '.' の数を数え、ans を更新
    for i in range(W - K + 1):
        if X[i+K] - X[i] == 0:
            ans = min(ans, D[i+K] - D[i])

# 4. 縦方向の探索
for col in range(W):
    # a. X と D の累積和を計算
    for i in range(H):
        X[i+1] = X[i] + (grid[i][col] == 'x')
        D[i+1] = D[i] + (grid[i][col] == '.')
    
    # b. 連続する K 個のマスについて、'x' がないかチェック
    # c. 'x' がない場合、その区間の '.' の数を数え、ans を更新
    for i in range(H - K + 1):
        if X[i+K] - X[i] == 0:
            ans = min(ans, D[i+K] - D[i])

# 5. 結果の出力
print(ans if ans != INF else -1)