競プロ典型90問：012 - Red Painting（★4）

問題

https://atcoder.jp/contests/typical90/tasks/typical90_l

挑戦結果

• 結果：できなかった
• 時間：30分ぐらい

考えたこと

• 囲碁っぽくやること。TLEした・・・。

公式解説

• UnionFindを思い出したし、以前にライブラリ化もしていた。

解説を読んだふりかえり

• UnionFindでやったらサクッとできた。
• ただし、UnionFindの高速化はやってないので、どこかで対応したほうが良さそう。

ソース

H, W = [int(x) for x in input().split()]
Q = int(input())

############################################
# Union Find 
# N = 100
N = (H+2) * (W+2)
PARENT = list(range(N))

def root(n):
    if PARENT[n] == n:
        return n
    else:
        ret = root(PARENT[n])
        PARENT[n] = ret
        return ret

def same(n1, n2):
    return root(n1) == root(n2)

def unite(n1, n2):
    n1 = root(n1)
    n2 = root(n2)
    if n1 == n2:
        return
    PARENT[n1] = n2
############################################

# 盤面が赤になっているか
B = [False] * N
# ２次元を1次元に変換
def rc2p(r,c):
    return (W+2)*r + c

# 1のクエリ(色を塗る)
def query1(r,c):
    pU = rc2p(r+1,c)
    pD = rc2p(r-1,c)
    pR = rc2p(r,c+1)
    pL = rc2p(r,c-1)
    p = rc2p(r,c)
    B[p] = True
    if B[pU]: unite(p,pU)
    if B[pD]: unite(p,pD)
    if B[pR]: unite(p,pR)
    if B[pL]: unite(p,pL)

# 2のクエリ(判定)
def query2(r1,c1, r2,c2):
    ans = "No"
    p1 = rc2p(r1,c1)
    p2 = rc2p(r2,c2)
    if same(p1,p2) and B[p1] and B[p2]:
        ans = "Yes"
    print(ans)

# メイン部分
for _ in range(Q):
    q = input().split()
    if q[0]=="1":
        query1(int(q[1]), int(q[2]))
    else:
        query2(int(q[1]), int(q[2]),int(q[3]), int(q[4]))