Submission #76711895

---

Source Code Expand

import sys
input = sys.stdin.readline

H, W = map(int, input().split())
grid = [input().strip() for _ in range(H)]

buildingid = [[-1] * W for _ in range(H)]
bldcnt = []
bid = 0

dirs = [(-1,0),(1,0),(0,-1),(0,1)]

for i in range(H):
    for j in range(W):
        if grid[i][j] == 'B':
            buildingid[i][j] = bid
            cnt = 0
            for di, dj in dirs:
                ni, nj = i+di, j+dj
                if 0 <= ni < H and 0 <= nj < W and grid[ni][nj] == 'R':
                    cnt += 1
            bldcnt.append(cnt)
            bid += 1

active = sum(1 for x in bldcnt if x > 0)

road = [[False]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if grid[i][j] == 'R':
            road[i][j] = True

Q = int(input())
out = []
vis = set()

def check(i, j):
    global active
    if grid[i][j] != 'B':
        return
    b = buildingid[i][j]
    if b in vis:
        return
    vis.add(b)
    if bldcnt[b] == 0:
        active += 1
    bldcnt[b] += 1

for _ in range(Q):
    U, D, L, R = map(int, input().split())
    U -= 1; D -= 1; L -= 1; R -= 1
    vis.clear()

    for j in range(L, R+1):
        if U > 0 and not road[U-1][j]:
            road[U-1][j] = True
            check(U-1, j)

    for j in range(L, R+1):
        if D+1 < H and not road[D+1][j]:
            road[D+1][j] = True
            check(D+1, j)

    for i in range(U, D+1):
        if L > 0 and not road[i][L-1]:
            road[i][L-1] = True
            check(i, L-1)

    for i in range(U, D+1):
        if R+1 < W and not road[i][R+1]:
            road[i][R+1] = True
            check(i, R+1)

    out.append(str(active))

print("\n".join(out))

Submission Info

Judge Result