翻译来源:loj #5461. 「ROI 2012 Day 2」迷雾中的刺猬。
河面上弥漫着浓雾,一匹悲伤的白马没入了雾中,雾气淹没了它的胸部。
“看,”刺猬说,“什么都看不见了,连爪子都看不见。”
“马儿!”他喊道。但马儿没有回应。“马儿去哪儿了?”刺猬心想。
(S.G. 科兹洛夫)
刺猬走进了迷雾,发现自己身处一个 米的矩形山谷中,山谷里有一匹马在游荡。刺猬想要找到它。我们假设在每个时刻,刺猬和马都位于 个格子中的一个。雾气非常浓,即使马和刺猬在同一格子内,刺猬也无法看见马。幸运的是,刺猬拥有非常敏锐的听觉,可以感知马儿相对于当前位置的移动方向。他还可以呼唤马儿,如果马儿与他位于同一格子内,马儿会听到并一定会回应。
在每个时刻,刺猬可以移动到水平、垂直或对角线方向的相邻格子。随后,他能清楚听到马儿相对于之前位置的移动方向。马儿在单位时间内只会沿水平或垂直方向移动一格(向左、向上、向右或向下)。马儿不会离开山谷边界,因此刺猬也不应离开。
你需要编写一个程序,帮助刺猬根据其初始位置和对马儿移动的追踪,尽快找到马儿。
交互方式
这是一个交互题。在运行过程中,程序将通过标准输入/输出流与模拟马儿行为的程序进行交互。
程序首先从标准输入流读取第一行的两个自然数 和 ,以及第二行的刺猬初始位置坐标——两个自然数 (列号)和 (行号)。每行中的数字以空格分隔。
随后,程序与模拟马儿行为的程序按照以下协议进行交互:
- 程序向标准输出流输出一行,描述刺猬的移动,包含三个数字:水平方向的移动偏移 、垂直方向的移动偏移 ,以及一个数字,表示刺猬是否在到达的新格子中呼唤马儿( 表示呼唤, 表示不呼唤)。输出需以换行符结束,并刷新输出缓冲区。为此,可使用:
- Pascal 或 Delphi 中的
flush(output);
- C/C++ 中的
fflush(stdout) 或 cout.flush();
- Visual Basic 中的
Console.out.flush()。
- 随后,程序从标准输入流读取模拟程序的响应,包含三个以空格分隔的数字。第一数字为 或 :
- 表示刺猬未尝试呼唤马儿或呼唤时马儿不在同一格子内,此时后两个数字表示马儿的水平移动偏移 和垂直移动偏移 ,且 和 中至少有一个为 ;
- 表示刺猬呼唤了马儿且马儿确实在同一格子内,此时后两个数字为 ,程序应结束运行。
程序不得超过 次移动。