P5195 [USACO05DEC] Knights of Ni S

Bessie has run into a big problem: she accidentally entered a castle in the forest. If she wants to go home, she must pass through this forest guarded by knights. To leave safely, Bessie has to follow the knights’ request: find a special kind of bush in the forest and bring one back to them. Of course, Bessie wants to leave this scary forest as soon as possible, so she must finish the task as quickly as she can. Bessie carries a map of the forest. The forest on the map is placed in a Cartesian coordinate system and is divided by unit lengths on the $x, y$ axes into $W \times H$ blocks $(1 \leq W, H \leq 1000)$. She has found on the map the positions of herself and the knights, and the map also marks the area where the needed bush grows. Some areas cannot be passed (for example, swamps, cliffs, and places where man-eating rabbits live). Before finding the bush, Bessie cannot pass through the block where the knights are located. To make sure she does not get lost, Bessie only moves in the four directions: due north, due east, due south, and due west (note that she does not move diagonally). It takes her exactly one day to move from one block to an adjacent block. Bessie wants you to help her compute the minimum number of days she needs to escape from this terrible place. The input guarantees that Bessie can complete the knights’ task.

The first line contains $2$ integers separated by spaces, i.e., $W, H$ mentioned in the statement. Next comes the map Bessie holds. Each line uses several digits to represent the terrain of the corresponding row on the map. The first line describes the northernmost row of land; the last line describes the southernmost row. Areas corresponding to adjacent digits are adjacent blocks. If the width of the map is less than or equal to $40$, then each line of digits corresponds to exactly one row of the map. If the width is greater than $40$, then each line provides only $40$ digits, and it is guaranteed that every line except the last contains exactly $40$ digits. No row of the map is split across two different input lines. The terrain represented by the digits on the map: - $0$: empty land that Bessie can pass through. - $1$: impassable area for various reasons. - $2$: Bessie’s current position. - $3$: the knights’ position. - $4$: land where the needed bush grows.

Output one positive integer, the minimum number of days Bessie must spend to complete the knights’ task.

The forest has length $8$ and width $4$. Bessie’s starting position is on row $3$, not far from the knights. Bessie can complete the task along this route: north, west, north, south, east, east, north, east, east, south, south. She gets the bush she needs in the northwest corner of the forest, then goes around obstacles and hands it to the knights in the southeast. Translated by ChatGPT 5