ABC 96C - Grid Repainting 2를 풀었다






몇 번 덮어쓰기(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) 程度。全探索しても余裕。

좋은 웹페이지 즐겨찾기