P1560 [USACO5.2] Snail Trails

Sally Snail likes to wander on an $N \times N$ board ($1

The first line contains $N$ — the size of the board, and $B$ — the number of obstacles ($1 \le B \le 200$). The next $B$ lines contain the positions of the obstacles. The sample input below corresponds to the example board above. The sample output below shows the answer to that instance. Note that when $N > 26$, the input file cannot denote obstacles beyond column Z. (You do not need to worry specifically about this — just continue from the ASCII code of A; whatever letters come next are fine.)

Output a single line with the maximum number of cells Sally can visit.

$$ \boxed{\quad\begin{aligned} \verb! A B C D E F G H! \\ \verb!1 S . . . . . # .! \\ \verb!2 | . . . # . . .! \\ \verb!3 | . . . +--------+! \\ \verb!4 | . . . | . . |! \\ \verb!5 +-----------+ # . |! \\ \verb!6 # . . . . . . |! \\ \verb!7 +------------------ |! \\ \verb!8 +--------------------+! \\ \end{aligned}\quad}$$ Translation from NOCOW. USACO Training Section 5.2. [This problem may contain issues; we do not guarantee that there exists a program that can pass all inputs that meet the requirements.](https://www.luogu.com.cn/discuss/1072919) If you believe your solution can pass all valid inputs, feel free to contact the administrators. Translated by ChatGPT 5