P2845 [USACO15DEC] Switching on the Lights S

Source: usaco-2015-dec. Farmer John recently built a large set of barns arranged in an $N \times N$ rectangular grid ($1 < N \leq 100$). However, Bessie is afraid of the dark and wants to know how many barns’ lights she can turn on.

There are $N \times N$ rooms forming an $N \times N$ grid. Bessie starts at the top-left corner $(1, 1)$ and can move only up, down, left, and right. Initially, only the room $(1, 1)$ is lit, and Bessie may only move through rooms whose lights are on. There are $M$ additional pieces of information. Each describes that a switch in room $(a, b)$ controls the light in room $(c, d)$. Compute the maximum number of rooms whose lights can be turned on.

The first line contains two integers $N, M$ ($1 < N \leq 100$, $1 < M < 2 \times 10^5$). Lines $2$ to $M+1$ each contain four integers $(x_1, y_1), (x_2, y_2)$, meaning the switch in room $(x_1, y_1)$ can turn on the light in room $(x_2, y_2)$.

Output a single integer, the maximum number of rooms that can be lit.

Bessie can use the switch at $(1, 1)$ to turn on the lights in $(1, 2)$ and $(1, 3)$, then move to $(1, 3)$ and turn on $(2, 1)$, move to $(2, 1)$ and turn on $(2, 2)$. The switch at $(2, 3)$ is unreachable. Therefore, $5$ rooms can be lit. Translated by ChatGPT 5