농부 존은 최근에 N × N개의 방이 있는 거대한 헛간을 새로 지었다. 각 방은 (1, 1)부터 (N,N)까지 번호가 매겨져있다(2 ≤ N ≤ 100). 어둠을 무서워하는 암소 베시는 최대한 많은 방에 불을 밝히고 싶어한다.
베시는 유일하게 불이 켜져있는 방인 (1, 1)방에서 출발한다. 어떤 방에는 다른 방의 불을 끄고 켤 수 있는 스위치가 달려있다. 예를 들어, (1, 1)방에 있는 스위치로 (1, 2)방의 불을 끄고 켤 수 있다. 베시는 불이 켜져있는 방으로만 들어갈 수 있고, 각 방에서는 상하좌우에 인접한 방으로 움직일 수 있다.
베시가 불을 켤 수 있는 방의 최대 개수를 구하시오.
입력
첫 번째 줄에는 N(2 ≤ N ≤ 100)과, M(1 ≤ M ≤ 20,000)이 정수로 주어진다.
다음 M줄에는 네 개의 정수 x, y, a, b가 주어진다. (x, y)방에서 (a, b)방의 불을 켜고 끌 수 있다는 의미이다. 한 방에 여러개의 스위치가 있을 수 있고, 하나의 불을 조절하는 스위치 역시 여러개 있을 수 있다.
import sys
sys.stdin=open('input.txt','r')
input=sys.stdin.readline
from collections import deque
moves=[(0,1),(-1,0),(0,-1),(1,0)]
def in_range(nx,ny):
return 0<=nx<N+1 and 0<=ny<N+1
if __name__=="__main__":
N,M=map(int, input().split())
board=[[[] for _ in range(N+1)] for _ in range(N+1)]
lights=[[0]*(N+1) for _ in range(N+1)]
lights[1][1]=1
Q=deque()
Q.append((1,1))
visited=[[0]*(N+1) for _ in range(N+1)]
visited[1][1]=1
for _ in range(M):
x,y,a,b=map(int, input().split())
board[x][y].append((a,b))
cnt=1
while Q:
x,y=Q.popleft()
# 현재 위치에서 스위치켜기
for tx,ty in board[x][y]:
if lights[tx][ty]==0:
lights[tx][ty]=1
cnt+=1
# 현재 스위치로 불이 켜진 방의 상하좌우를 살펴보고 연결 되어있고 이전에 방문한적이 있어도
# 다시 돌아와서 새롭게 불 켜진 방으로 돌아가야하므로
for dx,dy in moves:
nx=tx+dx
ny=ty+dy
# 불켜진 (tx,ty) 상하좌우에 접촉된 방문한 적있는 방이 있으면 다음에 돌아와서 불을 킬 수 있음
if in_range(nx,ny) and visited[nx][ny]==1:
Q.append((nx,ny))
for dx,dy in moves:
nx=x+dx
ny=y+dy
# 불켜진 현재 방 (x,y)에서 상하좌우 (nx,ny)에 불이 켜졌으면 이동 가능
if in_range(nx,ny) and lights[nx][ny]==1 and visited[nx][ny]==0:
Q.append((nx,ny))
visited[nx][ny]=1
print(cnt)
