P1519 [USACO2.4] Overfencing

Farmer John built a huge maze enclosed by fences out in the field. Fortunately, he left two fence openings on the boundary of the maze as exits. Even better, the maze he built is “perfect”: from any point in the maze you can find a path to an exit. Given the width $W$ ($1 \leq W \leq 38$) and height $H$ ($1 \leq H \leq 100$), a maze is described by $2 \times H+1$ lines, each with $2 \times W+1$ characters in the format shown below. Compute the number of steps needed to exit the maze from the “worst” starting cell (i.e., even if you head optimally toward the nearest exit from that cell, it still requires the most steps). Cows move only horizontally or vertically along the X or Y axes; they never move diagonally. Moving into a new cell counts as one step (including the step that moves out of the maze). Here is a maze with $W=5, H=3$: ```plain +-+-+-+-+-+ | | +-+ +-+ + + | | | | + +-+-+ + + | | | +-+ +-+-+-+ ``` In the example above, fence posts appear only in odd-numbered rows or odd-numbered columns. Each maze has exactly two exits.

The first line contains two integers $W,H$. Then follow $2 \times H+1$ lines: each line has $2 \times W+1$ characters describing a maze.

Output a single integer: the minimal number of steps to exit the maze in the worst case.

Translation from NOCOW. USACO 2.4. Translated by ChatGPT 5