불켜기 - BOJ

불켜기 - BOJ

from collections import deque

dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]

d = dict()
N, M = map(int, input().split())
visit = [[False] * N for _ in range(N)]
tmp = [[False] * N for _ in range(N)]
on = [[False] * N for _ in range(N)]

for _ in range(M):
    x, y, a, b = map(int, input().split())
    d[(x - 1, y - 1)] = d.get((x - 1, y - 1), []) + [(a - 1, b - 1)]

q = deque()
q.append([0, 0])
visit[0][0] = True
tmp[0][0] = True
on[0][0] = True

while q:
    x, y = q.popleft()
    if d.get((x, y), None):
        for a, b in d[(x, y)]:
            if visit[a][b]: continue
            if tmp[a][b]:
                q.append([a, b])
                visit[a][b] = True
            on[a][b] = True
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or ny < 0 or nx >= N or ny >= N or visit[nx][ny]:
            continue
        if on[nx][ny]:
            visit[nx][ny] = True
            q.append([nx, ny])
        else:
            tmp[nx][ny] = True

cnt = 0
for i in range(N):
    for j in range(N):
        if on[i][j]:
            cnt += 1
print(cnt)