P2199 The Final Maze

As the fourth champion in the Triwizard Tournament, Harry Potter has braved many dangers to reach the final task — the maze. Now only Harry and Cedric are left in the maze. Harry can win the competition only if he gets to the trophy before Cedric. As long as Harry can see the trophy, he can use a Summoning Charm to pull it to himself. So the question is how Harry can see the trophy as soon as possible.

Harry has excellent eyesight: he can look in a straight line from one side of the maze to the other (but only in eight directions — NE, E, SE, S, SW, W, NW, N). He also runs very fast: taking one step (moving one cell up, down, left, or right) costs only $1\text{s}$. However, the maze walls are opaque, and burning them down is not easy, so Harry decides to run to a place where he can see the trophy. Now he wants you to determine the minimum time needed for him to obtain the trophy.

The first line contains $2$ numbers $N, M$ indicating the size of the maze ($N$ is height, $M$ is width). Next comes the $N \times M$ maze: $\texttt{O}$ denotes open ground, and $\texttt{X}$ denotes a wall. Finally, there are multiple pairs of data, each giving the coordinates of the trophy and Harry (obviously not on walls), one pair per line. A single $0$ marks the end.

For each pair of data, output the minimum time for Harry to obtain the trophy, one per line. If the Ministry of Magic makes things difficult by surrounding the trophy with walls, output $\texttt{Poor Harry}$.

For $30\%$ of the testdata, $N \times M \le 100$. For $60\%$ of the testdata, $N \times M \le 1600$. For $100\%$ of the testdata, $N \times M \le 16384$. The number of query pairs does not exceed $512$. Translated by ChatGPT 5