레이팅 미적용농부 존은 최근 \(N \times N\) 격자 형태의 방들로 이루어진 거대한 헛간(\(2 \leq N \leq 100\))을 지었다. 방들은 \((1,1)\)부터 \((N,N)\)까지 번호가 붙어 있다. 어둠을 다소 무서워하는 소 베시는 최대한 많은 방의 전등을 켜고 싶다.
베시는 처음에 유일하게 불이 켜져 있는 방인 \((1,1)\)에서 출발한다. 일부 방에는 다른 방의 전등을 껐다 켰다 할 수 있는 스위치가 있다. 예를 들어 방 \((1,1)\)에 방 \((1,2)\)의 전등을 토글하는 스위치가 있을 수 있다. 베시는 불이 켜진 방으로만 이동할 수 있으며, 방 \((x,y)\)에서 인접한 네 방 \((x-1,y)\), \((x+1,y)\), \((x,y-1)\), \((x,y+1)\)로만 이동할 수 있다(방이 격자의 경계에 있으면 이웃이 더 적을 수 있다).
베시가 불을 켤 수 있는 방의 최대 개수를 구하시오.
Problem credits: Austin Bannister and Brian Dean
Problem credits: Austin Bannister and Brian Dean
입력의 첫째 줄에 정수 \(N\)과 \(M\)(\(1 \leq M \leq 20,000\))이 주어진다.
다음 \(M\)개의 줄에는 각각 스위치 하나를 나타내는 네 정수 \(x\), \(y\), \(a\), \(b\)가 주어지며, 이는 방 \((x,y)\)에 있는 스위치로 방 \((a,b)\)의 전등을 토글할 수 있음을 의미한다. 한 방에 여러 개의 스위치가 있을 수 있고, 여러 스위치가 같은 방의 전등을 토글할 수도 있다.
베시가 불을 켤 수 있는 방의 최대 개수를 한 줄에 출력한다.
lightson.in · 출력을 쓸 파일 lightson.out
3 6
1 1 1 2
2 1 2 2
1 1 1 3
2 3 3 1
1 3 1 2
1 3 2 15Here, Bessie can use the switch in \((1,1)\) to turn on
lights in \((1,2)\) and \((1,3)\). She can then walk to \((1,3)\) and turn on the lights in
\((2,1)\), from which she can turn on the lights in \((2,2)\). The switch in
\((2,3)\) is inaccessible to her, being in an unlit room. She can therefore
illuminate at most 5 rooms.
riseoj 작성
출처 올림피아드 > USACO > 2015-2016 > December > Silver