Pythonで理解する蟻本「3-2 領域の個数」(p.150)

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の
「3-2 領域の個数」(p.150)
のコードをPythonで書き直したものとなっています。

入力

入力例

10 10 5
1 1 4 9 10
6 10 4 9 10
4 8 1 1 6
4 8 10 5 10

解答

from collections import deque

# 入力
W, H, N = map(int,input().split())
X1 = list(map(int,input().split()))
X2 = list(map(int,input().split()))
Y1 = list(map(int,input().split()))
Y2 = list(map(int,input().split()))

# 塗りつぶし用
fld = [[False] * (N * 6) for _ in range(N * 6)]

# x1, x2を座標圧縮し、座標圧縮した際の幅を返す
def compress(x1, x2, w):
    xs = []
    
    for i in range(N):
        for d in range(-1, 2):
            tx1 = x1[i] + d
            tx2 = x2[i] + d
            if 1 <= tx1 <= W:
                xs.append(tx1)
            if 1 <= tx2 <= W:
                xs.append(tx2)
    xs = list(set(xs))
    xs.sort()
    
    for i in range(N):
        x1[i] = xs.index(x1[i])
        x2[i] = xs.index(x2[i])
    
    return x1, x2, len(xs)

# 座標圧縮
X1, X2, W = compress(X1, X2, W)
Y1, Y2, H = compress(Y1, Y2, H)

# 腺のある部分を塗りつぶし
for i in range(N):
    for y in range(Y1[i], Y2[i] + 1):
        for x in range(X1[i], X2[i] + 1):
            fld[y][x] = True

# 領域を数える
ans = 0
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
for y in range(H):
    for x in range(W):
        if fld[y][x]:
            continue
        ans += 1
        
        # 幅優先探索
        que = deque([(x, y)])
        while len(que) != 0:
            sx, sy = que.popleft()
            
            for i in range(4):
                tx = sx + dx[i]
                ty = sy + dy[i]
                if tx < 0 or W <= tx or ty < 0 or H <= ty:
                    continue
                if fld[ty][tx]:
                    continue
                que.append((tx, ty))
                fld[ty][tx] = True

print(ans)