競プロキャンプ2026関西 D - Flowers
- サイト
- MOFE
- コンテスト
- 競プロキャンプ2026関西
- 問題
- D - Flowers
のマス目に、十字形(中心とその上下左右の 5 マス)の「花」が、はみ出さず重ならないようにいくつか描かれています。描かれたマスが # で与えられるので、すべての花の中心を求める問題です()。
マス目を上の行から順に、各行は左から順に見ていきます。最初に見つかった # は、ある花の一番上のマスです。花の 5 マスのうち、一番上のマスだけがほかの 4 マスより上の行にあり、見る順番が最も早いからです。
そこで、# が見つかったら、その 1 つ下を中心とする花を答えに加え、その花の 5 マスを . に戻します。こうすると、次に見つかる # も、残っている花のどれかの一番上のマスになります。残っている花のマスより前にあるマスは、すべて見終わっていて、そこにあった花は消してあるからです。
最後まで見れば、すべての花の中心が求まります。計算量は です。
Python
from itertools import product
H, W = map(int, input().split())S = [list(input()) for i in range(H)]ans = []for i, j in product(range(H), range(W)): if S[i][j] == "#": ans.append((i + 2, j + 1)) S[i][j] = "." S[i + 1][j - 1] = "." S[i + 1][j] = "." S[i + 1][j + 1] = "." S[i + 2][j] = "."print(len(ans))for x, y in ans: print(x, y)product(range(H), range(W)) は、上の行から順に、各行は左から順に (i, j) を並べます。コードの座標は 0 始まりなので、中心 を 1 始まりに直した (i + 2, j + 1) を答えに加えています。花ははみ出さないように描かれているので、S[i + 2][j] などの添字が範囲外になることはありません。