Switching on the Lights#11157
Farmer John has recently built an enormous barn consisting of an n \times n grid of rooms, numbered from to . 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 , the only room that is initially lit. In some rooms, she will find light switches that she can use to turn on the lights in other rooms. For example, there might be a switch in room that turns on the lights in room . Bessie can only travel through rooms whose lights are on, and she can move from a room only to one of its four adjacent neighbors: (x - 1, y), (x + 1, y), (x, y - 1), or (x, y + 1) (or to fewer neighbors if the room is on the boundary of the grid).
Determine the maximum number of rooms whose lights Bessie can turn on.
The first line contains two integers and m~(2 \le n \le 100, 1 \le m \le 20000).
Each of the next lines describes a single light switch using four integers x, y, a, and . A switch in room can be used to turn on the lights in room . Multiple switches may be located in the same room, and multiple switches may turn on the lights in the same room.
Print one integer — the maximum number of rooms Bessie can illuminate.
In this example, Bessie can use the switch in to turn on the lights in and . She can then walk to and turn on the lights in , from which she can turn on the lights in . The switch in is inaccessible because it is located in an unlit room. Therefore, Bessie can illuminate at most rooms.
Example 1