問題概要

H*Wのマスに白マス'.'と黒マス'#'がある。1ターンで、黒マスを中心とする十字に塗り潰すことができる。何ターンで全てのマスが黒マスになるか。

考えたこと(間違い)

最初に、黒マスを取得し、1 ターンごと塗りつぶすマスをキューにぶち込んで黒くする。キューが空になるまで繰り返す。

TLEで死んだ。

""" TLE """
from collections import deque


def main():
    h, w = [int(i) for i in input().split()]
    f = []
    black = deque()
    for i in range(h):
        line = list(input())
        for j, c in enumerate(line):
            if c == '#':
                black.appendleft((i, j))
        f.append(line)
    ans = 0
    d = [[False for i in range(w)] for j in range(h)]
    black.appendleft((-1, -1))
    sw = False
    while black:
        y, x = black.pop()
        if (y, x) == (-1, -1) and sw:
            break
        else:
            sw = False
        if (y, x) == (-1, -1):
            sw = True
            ans += 1
            black.appendleft((-1, -1))
        for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            if 0 <= y+dy < h and 0 <= x+dx < w and f[y+dy][x+dx] == '.' and \
                d[y+dy][x+dx] == False:
                f[y+dy][x+dx] = '#'
                d[y+dy][x+dx] = True
                black.appendleft((y+dy, x+dx))
    print(ans-1)


if __name__ == '__main__':
    main()

別マップを用意して、訪れたか確認してたんだけど、どうしてもダメだった。ターンごとのマスを識別するために(-1, -1)の組みを入れたんだけど、全然だった。

けんちょんさんのC++コードを書き直してもTLE。こんな感じ

from collections import deque


def main():
    h, w = [int(i) for i in input().split()]
    f = []
    for i in range(h):
        f.append(list(input()))
    #カウンター用のフィールド
    d = [[-1 for j in range(w)] for i in range(h)]
    q = deque()
    for i in range(h):
        for j in range(w):
            if f[i][j] == '#':
                # スタート地点のメモ
                d[i][j] = 0
                q.appendleft((i, j))

    while q:
        y, x = q.pop()
        for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            ny, nx = y+dy, x+dx
            # 行ったことない場合に限る
            if 0 <= ny < h and  0 <= nx < w and d[ny][nx] == -1:
                d[ny][nx] = d[y][x] + 1
                q.appendleft((ny, nx))

    ans = 0
    for i in range(h):
        for j in range(w):
            ans = max(ans, d[i][j])
    print(ans)


if __name__ == '__main__':
    main()

けんちょんさんのは、別マップにターン数を書いて保存したやつで、自分とは考えが違かったんだな、なるほどなと思った。ちなみに、TLEだったけど、けんちょんさんのは、TLEが 1 つ減ったりして、勉強になった。 TLEが取れなくて、こんな日もあるんでしょうという気持ちになった日でした。

あ、今日は vue と OS の記事書きません。

いろんなことで四苦Hack（仮）

b1u3の技術ブログ

AGC 033 A - Darker and Darker

問題概要

考えたこと(間違い)