P15300 [ROI 2012 Day 2] horse 迷雾中的刺猬

翻译来源：[loj #5461. 「ROI 2012 Day 2」迷雾中的刺猬](https://loj.ac/p/5461)。 > 河面上弥漫着浓雾，一匹悲伤的白马没入了雾中，雾气淹没了它的胸部。 > > “看，”刺猬说，“什么都看不见了，连爪子都看不见。” > > “马儿！”他喊道。但马儿没有回应。“马儿去哪儿了？”刺猬心想。 > > （S.G. 科兹洛夫）

刺猬走进了迷雾，发现自己身处一个 $N \times M$ 米的矩形山谷中，山谷里有一匹马在游荡。刺猬想要找到它。我们假设在每个时刻，刺猬和马都位于 $N \times M$ 个格子中的一个。雾气非常浓，即使马和刺猬在同一格子内，刺猬也无法看见马。幸运的是，刺猬拥有非常敏锐的听觉，可以感知马儿相对于当前位置的移动方向。他还可以呼唤马儿，如果马儿与他位于同一格子内，马儿会听到并一定会回应。 在每个时刻，刺猬可以移动到水平、垂直或对角线方向的相邻格子。随后，他能清楚听到马儿相对于之前位置的移动方向。马儿在单位时间内只会沿水平或垂直方向移动一格（向左、向上、向右或向下）。马儿不会离开山谷边界，因此刺猬也不应离开。 你需要编写一个程序，帮助刺猬根据其初始位置和对马儿移动的追踪，尽快找到马儿。 ### 交互方式 这是一个交互题。在运行过程中，程序将通过标准输入/输出流与模拟马儿行为的程序进行交互。 程序首先从标准输入流读取第一行的两个自然数 $N$ 和 $M$，以及第二行的刺猬初始位置坐标——两个自然数 $x_0$（列号）和 $y_0$（行号）$(1 \leq x_0 \leq M, 1 \leq y_0 \leq N)$。每行中的数字以空格分隔。 随后，程序与模拟马儿行为的程序按照以下协议进行交互： 1. 程序向标准输出流输出一行，描述刺猬的移动，包含三个数字：水平方向的移动偏移 $dx$ $(dx = -1, 0, 1)$、垂直方向的移动偏移 $dy$ $(dy = -1, 0, 1)$，以及一个数字，表示刺猬是否在到达的新格子中呼唤马儿（$1$ 表示呼唤，$0$ 表示不呼唤）。输出需以换行符结束，并刷新输出缓冲区。为此，可使用： - Pascal 或 Delphi 中的 `flush(output)`； - C/C++ 中的 `fflush(stdout)` 或 `cout.flush()`； - Visual Basic 中的 `Console.out.flush()`。 2. 随后，程序从标准输入流读取模拟程序的响应，包含三个以空格分隔的数字。第一数字为 $0$ 或 $1$： - $0$ 表示刺猬未尝试呼唤马儿或呼唤时马儿不在同一格子内，此时后两个数字表示马儿的水平移动偏移 $dx$ $(dx = -1, 0, 1)$ 和垂直移动偏移 $dy$ $(dy = -1, 0, 1)$，且 $dx$ 和 $dy$ 中至少有一个为 $0$； - $1$ 表示刺猬呼唤了马儿且马儿确实在同一格子内，此时后两个数字为 $0$，程序应结束运行。 程序不得超过 $10,000$ 次移动。

无

无

 刺猬初始位置在格子 $(1, 2)$。首先，他尝试在当前格子呼唤马儿（输出：`0 0 1`），但马儿不在此，馬儿向右移动（输入：`0 1 0`）。刺猬沿对角线移动但未呼唤（输出：`1 -1 0`），马儿留在原地（输入：`0 0 0`）。刺猬向右移动并呼唤马儿（输出：`1 0 1`）。马儿在同一格子内并回应（输入：`1 0 0`）。因此，马儿初始位置在 $(2, 1)$，他们在 $(3, 1)$ 相遇。刺猬共移动了三次，呼唤了两次。 评分公式为 $\min\{10, \operatorname{round}(10 \times (J/S)^2)\}$，其中测试点满分为 $10$，$S$ 为程序找到马儿所需的移动次数，$J$ 为给定参考解在相同初始位置下所需的移动次数。 详细子任务附加限制及分值如下表所示： | 子任务 | 分值 | 附加限制 | 说明 | | :----: | :--: | :---------------------------------: | :-----------------------------------------------: | | $1$ | $40$ | $2 \leq N, M \leq 10$ | 每个测试点独立评分 | | $2$ | $60$ | $2 \leq N, M \leq 30$，呼唤次数不超过 $N \times M$ | 每个测试点独立评分 | 为测试你的代码，可使用位于「文件」下的辅助程序 `runpair`。该程序可同时运行两个程序，并将一个程序的标准输出流重定向到另一个程序的标准输入流，反之亦然。为测试解决方案，除编写解决方案程序外，还需编写模拟马儿行为的程序。使用命令 `runpair "马儿可执行文件" "刺猬可执行文件"` 可同时运行两者，并在屏幕上显示它们的交互对话。