DDCC2020 C - Strawberry Cakes

問題原文

C - Strawberry Cakes

問題要旨

のグリッドが与えられ、その区画のうち 個 にはイチゴが乗っている。このグリッドを以下の条件のように分割する方法を構築 せよ。

• 分割された各区画はちょうど つのイチゴを含む。
• 分割された各区間は長方形（正方形も含む）である。

考えたこと

• 各行について横向きに塗れば良さそう。行が変わる or イチゴを見つけたら 塗る色を変える。
• イチゴがない行は無視してよさそう。

難しいこと

• イチゴがない行が連続する時どうしよう？
• 行が変わったら違う色に変える？ → 先頭列にイチゴがあったら？途中にあったら？

考えるべきこと

• イチゴがない行は無視して、後から 「１つ上の行を見ながら下向きにくだる」 と 「１つ下の行を見ながら上向きにのぼる」 をすれば良い。
• 各行最初に見つけたイチゴでは色を変えなくて良い。（行が変わることで色が変わっているので）

実装

H, W, K = map(int, input().split())
G = [list(input()) for i in range(H)]


# イチゴがない行の番号を記録しておく
non_placed_row_indexes = set()
for h in range(H):
    if G[h].count('#') == 0:
        non_placed_row_indexes.add(h)


ans = [[0] * W for i in range(H)]
painting = 0
for h in range(H):
    # イチゴがない行なら何もしない
    if h in non_placed_row_indexes:
        continue

    # 各行最初のイチゴが見つかったか
    find_flg = False
    for w in range(W):
        # 行が変わる
        if w == 0:
            painting += 1

        # イチゴを見つける
        if G[h][w] == '#':
            if find_flg:
                painting += 1
            else:
                # 見つけたのがその行最初のイチゴなら色を変えなくてよい
                find_flg = True

        ans[h][w] = painting


# １つ上の行を見ながら下にくだる
for h in range(1, H):
    # イチゴがある行なら何もしない
    if h not in non_placed_row_indexes:
        continue

    for w in range(W):
        # １つ上の行の色をコピー
        ans[h][w] = ans[h - 1][w]

# １つ下の行を見ながら上にのぼる
for h in range(H - 2, -1, -1):
    # イチゴがある行なら何もしない
    if h not in non_placed_row_indexes:
        continue

    for w in range(W):
        # １つ下の行の色をコピー
        ans[h][w] = ans[h + 1][w]


# 出力
for a in ans:
    print(*a, sep=' ')

所感

落ち着けばなんのことはないんだけどなぁ。