ABC 96C - Grid Repainting 2 を解いた

5684 ワード
AtCoder Python AtCoderBeginnerContest Python テキストリンク




何回上書き(0回でも可)って書いてあるけど。
結局、"#" を発見した時に上下左右のうち、何れかに "#" があれば OK じゃね？っと考えた。
あとは for 文で全探索。

例えば1行目とか、普通に上下左右って探索しても error になるし、
どうしよっかなーって思ったけど以下の記述に落ち着いた。

GridRepainting2.py
H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]

#print(S)

for h in range(H):#O(50)
    for w in range(W):#O(50)
        lis = []

        if S[h][w] == "#":                      # もし"#" を発見したら。。
            if h-1 >= 0: lis.append(S[h-1][w])  #   1.上
            if h+1 <= H-1:lis.append(S[h+1][w]) #   2.下
            if w-1 >= 0: lis.append(S[h][w-1])  #   3.左
            if w+1 <= W-1:lis.append(S[h][w+1]) #   4.右　を lis に append

            # list の in 演算子は O(N)だけど、上下左右でも O(4)
            if "#" in lis:                      #  lis の中に "#" があれば連続したセルがあることになる
                continue
            else:
                print("No")                     #  無かった瞬間に No で break
                exit()
print("Yes")


##total 計算量は最低でも O(1000) 程度。全探索しても余裕。