P15300 [ROI 2012 Day 2] horse The Hedgehog in the Fog

Translation source: [loj #5461. "ROI 2012 Day 2" The Hedgehog in the Fog](https://loj.ac/p/5461). > Thick fog spread over the river. A sad white horse walked into the fog, and the fog covered its chest. > > "Look," said the hedgehog, "nothing can be seen anymore, not even my paws." > > "Horse!" he shouted. But the horse did not respond. "Where did the horse go?" the hedgehog thought. > > (S.G. Kozlov).

The hedgehog walks into the fog and finds himself in a rectangular valley of size $N \times M$ meters, where a horse is wandering. The hedgehog wants to find it. We assume that at every moment, the hedgehog and the horse are each located in one of the $N \times M$ cells. The fog is so thick that even if the horse and the hedgehog are in the same cell, the hedgehog still cannot see the horse. Fortunately, the hedgehog has very sharp hearing and can sense the direction of the horse's movement relative to its current position. He can also call the horse; if the horse is in the same cell as him, the horse will hear it and will definitely respond. At every moment, the hedgehog may move to a neighboring cell horizontally, vertically, or diagonally. Then, he can clearly hear the direction of the horse's movement relative to its previous position. The horse, in one unit of time, moves exactly one cell horizontally or vertically (left, up, right, or down). The horse never leaves the valley boundary, so the hedgehog should not leave it either. You need to write a program to help the hedgehog, based on its initial position and the tracking of the horse's movements, find the horse as quickly as possible. ### Interaction This is an interactive problem. During execution, your program interacts via standard input/output with a program that simulates the horse's behavior. First, your program reads from standard input the first line containing two natural numbers $N$ and $M$, and the second line containing the hedgehog's initial position coordinates, two natural numbers $x_0$ (column) and $y_0$ (row) $(1 \leq x_0 \leq M, 1 \leq y_0 \leq N)$. The numbers on each line are separated by spaces. After that, your program and the simulator follow this protocol: 1. Your program outputs one line to standard output describing the hedgehog's move, containing three numbers: the horizontal offset $dx$ $(dx = -1, 0, 1)$, the vertical offset $dy$ $(dy = -1, 0, 1)$, and a number indicating whether the hedgehog calls the horse after arriving at the new cell ($1$ means call, $0$ means do not call). The output must end with a newline and you must flush the output buffer. For this, you may use: - `flush(output)` in Pascal or Delphi. - `fflush(stdout)` or `cout.flush()` in C/C++. - `Console.out.flush()` in Visual Basic. 2. Then, your program reads the simulator's response from standard input, containing three space-separated numbers. The first number is $0$ or $1$: - $0$ means the hedgehog either did not try to call the horse, or it called but the horse was not in the same cell. In this case, the next two numbers are the horse's horizontal offset $dx$ $(dx = -1, 0, 1)$ and vertical offset $dy$ $(dy = -1, 0, 1)$, and at least one of $dx$ and $dy$ equals $0$. - $1$ means the hedgehog called the horse and the horse was indeed in the same cell. In this case, the next two numbers are $0$, and your program should terminate. Your program must not exceed $10{,}000$ moves.

N/A

N/A

 The hedgehog's initial position is at cell $(1, 2)$. First, it tries to call the horse in the current cell (output: `0 0 1`), but the horse is not there; the horse moves right (input: `0 1 0`). The hedgehog moves diagonally without calling (output: `1 -1 0`), and the horse stays in place (input: `0 0 0`). The hedgehog moves right and calls (output: `1 0 1`). The horse is in the same cell and responds (input: `1 0 0`). Therefore, the horse's initial position was at $(2, 1)$, and they meet at $(3, 1)$. The hedgehog moved three times and called twice. The scoring formula is $\min\{10, \operatorname{round}(10 \times (J/S)^2)\}$, where a test case has full score $10$, $S$ is the number of moves your program needs to find the horse, and $J$ is the number of moves needed by the given reference solution under the same initial position. The detailed subtasks, additional constraints, and scores are given in the table below: | Subtask | Score | Additional Constraints | Notes | | :-----: | :---: | :--------------------: | :---: | | $1$ | $40$ | $2 \leq N, M \leq 10$ | Each test case is scored independently. | | $2$ | $60$ | $2 \leq N, M \leq 30$, the number of calls does not exceed $N \times M$ | Each test case is scored independently. | To test your code, you may use the helper program `runpair` under "Files". This program can run two programs at the same time and redirect the standard output of one program to the standard input of the other, and vice versa. To test a solution, besides writing the solution program, you also need to write a program that simulates the horse's behavior. Using the command `runpair "horse executable" "hedgehog executable"` will run both at the same time and display their interactive dialogue on the screen. Translated by ChatGPT 5