题目描述

译自 ROI 2012 Day2 T3. Ёжик в тумане

河面上弥漫着浓雾，一匹悲伤的白马没入了雾中，雾气淹没了它的胸部。

“看，”刺猬说，“什么都看不见了，连爪子都看不见。”

“马儿！”他喊道。但马儿没有回应。“马儿去哪儿了？”刺猬心想。

（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$ 次移动。

2 3
1 2
0 1 0
0 0 0
1 0 0

0 0 1
1 -1 0
1 0 1

刺猬初始位置在格子 $(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$ 为给定参考解在相同初始位置下所需的移动次数。

详细子任务附加限制及分值如下表所示：

为测试你的代码，可使用位于「文件」下的辅助程序 runpair。该程序可同时运行两个程序，并将一个程序的标准输出流重定向到另一个程序的标准输入流，反之亦然。为测试解决方案，除编写解决方案程序外，还需编写模拟马儿行为的程序。使用命令 runpair "马儿可执行文件" "刺猬可执行文件" 可同时运行两者，并在屏幕上显示它们的交互对话。