コンテンツにスキップ

競プロキャンプ2026関西 D - Flowers

サイト
MOFE
コンテスト
競プロキャンプ2026関西
問題
D - Flowers

H×WH \times W のマス目に、十字形(中心とその上下左右の 5 マス)の「花」が、はみ出さず重ならないようにいくつか描かれています。描かれたマスが # で与えられるので、すべての花の中心を求める問題です(3≤H,W≤10003 \le H, W \le 1000)。

マス目を上の行から順に、各行は左から順に見ていきます。最初に見つかった # は、ある花の一番上のマスです。花の 5 マスのうち、一番上のマスだけがほかの 4 マスより上の行にあり、見る順番が最も早いからです。

そこで、# が見つかったら、その 1 つ下を中心とする花を答えに加え、その花の 5 マスを . に戻します。こうすると、次に見つかる # も、残っている花のどれかの一番上のマスになります。残っている花のマスより前にあるマスは、すべて見終わっていて、そこにあった花は消してあるからです。

最後まで見れば、すべての花の中心が求まります。計算量は O(HW)O(HW) です。

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 始まりなので、中心 (i+1,j)(i + 1, j) を 1 始まりに直した (i + 2, j + 1) を答えに加えています。花ははみ出さないように描かれているので、S[i + 2][j] などの添字が範囲外になることはありません。