Switching on the Lights
골드 II의견: 0
Farmer John has recently built an enormous barn consisting of an \(N \times N\)
grid of rooms (\(2 \leq N \leq 100\)), numbered from \((1,1)\) up to \((N,N)\). Being
somewhat afraid of the dark, Bessie the cow wants to turn on the lights in as
many rooms as possible.
Bessie starts in room \((1,1)\), the only room that is initially lit.
In some rooms, she will find light switches that she can use to toggle
the lights in other rooms; for example there might be a switch in room
\((1,1)\) that toggles the lights in room \((1,2)\). Bessie can only
travel through lit rooms, and she can only move from a room \((x,y)\) to
its four adjacent neighbors \((x-1,y)\), \((x+1,y)\), \((x,y-1)\) and
\((x,y+1)\) (or possibly fewer neighbors if this room is on the boundary
of the grid).
Please determine the maximum number of rooms Bessie can illuminate.
Problem credits: Austin Bannister and Brian Dean
Problem credits: Austin Bannister and Brian Dean
The first line of input contains integers \(N\) and \(M\) ($1 \leq M \leq
20,000$).
The next \(M\) lines each describe a single light switch
with four integers \(x\), \(y\), \(a\), \(b\), that a switch in room \((x,y)\)
can be used to toggle the lights in room \((a,b)\). Multiple switches
may exist in any room, and multiple switches may toggle the lights of
any room.
A single line giving the maximum number of rooms Bessie can
illuminate.
lightson.inlightson.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
평가 및 의견
Switching on the Lights
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Switching on the Lights