题目描述

机器人在一个由方形格子组成的地图上沿海岸线逆时针移动。每个格子被标记为陆地（$1$）或海洋（$0$）。机器人始终站在海岸线上（即其八邻域中至少有一个海洋格子），且海洋在其右侧。给定机器人当前的位置 $(x,y)$ 和朝向 $d$（$0$ 表示北，方向按顺时针编码 $0$ 到 $7$），以及其周围 $8$ 个格子的陆地/海洋状态（以相对坐标给出），要求决定机器人下一步应移动的方向（也是 $0$ 到 $7$ 的编码），以便继续沿海岸线逆时针移动。

输入格式

输入包含多个测试用例。每个测试用例第一行为三个整数 $x,y,d$，表示机器人当前位置和朝向。随后 $8$ 行，每行三个整数 $x_i,y_i,s_i$，表示相对于机器人位置的偏移量和该格子的状态（$1$ 为陆地，$0$ 为海洋）。输入以 $x=0$ 结束。

输出格式

对于每个测试用例，输出一行，包含一个整数 $nd$，表示机器人下一步应移动的方向。

样例输入

1 0 1
...
0

样例输出

1

题目分析

机器人沿海岸线逆时针移动，保持海洋在其右侧。给定周围 $8$ 个格子的信息，需要根据当前朝向和周围状态选择下一个移动方向。由于机器人沿逆时针方向追踪海岸，其移动策略可总结为：从当前朝向开始，顺时针方向扫描周围 $8$ 个方向，找到第一个为陆地的格子，机器人就向该方向移动。这是典型的“右转优先”海岸线跟踪算法，确保机器人始终贴着海岸线移动。

解题思路

实现步骤确定如下：

步骤 $\text{1}$. 读入当前位置 $(x,y)$ 和朝向 $d$。若 $x=0$ 则结束。

步骤 $\text{2}$. 读入 $8$ 个相邻格子的状态，将其映射到以机器人位置为中心的 $3\times 3$ 局部坐标系中，中心为机器人所在格（状态始终为陆地），但输入只给周围 $8$ 格。

步骤 $\text{3}$. 定义方向编码：$0$ 为北，$1$ 为东北，$2$ 为东，$3$ 为东南，$4$ 为南，$5$ 为西南，$6$ 为西，$7$ 为西北。对应的偏移量为 {0,1}, {-1,1}, {-1,0}, {-1,-1}, {0,-1}, {1,-1}, {1,0}, {1,1}}（注意坐标行、列与常规方向的关系，代码中实际使用了特定映射）。

步骤 $\text{4}$. 从当前朝向 $d$ 开始，沿顺时针方向（即 $d$ 增加）扫描 $8$ 个方向。对每个候选方向 $nd$，计算该方向上的相邻格子坐标 $(nx,ny)$，检查该格子是否为陆地（$s=1$）。找到第一个陆地格子，输出该方向并结束。

由于机器人始终站在海岸线上，且海洋在其右侧，该扫描顺序能保证机器人沿逆时针方向跟踪海岸。实际代码中，next 数组定义了从当前方向转向的优先级顺序，但通用解法为从 $d$ 开始顺时针扫描。

代码实现

// Coast Tracker
// UVa ID: 824
// Verdict: Accepted
// Submission Date: 2016-12-14
// UVa Run Time: 0.000s
//
// 版权所有（C）2016，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>

using namespace std;

int main(int argc, char *argv[])
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

    int offset[8][2] = {{0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}, {1, 0}, {1, 1}};
    int next[8]= {6, 6, 0, 0, 2, 2, 4, 4};
    int x, y, d, xi, yi, si;
    int surface[3][3];

    while (cin >> x, x > 0)
    {
        cin >> y >> d;
        for (int i = 0; i < 8; i++)
        {
            cin >> xi >> yi >> si;
            surface[xi - x + 1][yi - y + 1] = si;
        }
        
        for (int i = 0; i < 8; i++)
        {
            int nextd = (next[d] + i) % 8;
            int nextx = 1 + offset[nextd][0];
            int nexty = 1 + offset[nextd][1];
            
            if (surface[nextx][nexty])
            {
                cout << nextd << '\n';
                break;
            }
        }
    }
    
    return 0;
}

总结

本题通过模拟机器人感知和决策过程，实现海岸线跟踪。核心策略是从当前朝向开始顺时针扫描邻域，选择第一个陆地格子作为下一步移动方向。这种贪心策略确保机器人沿逆时针方向紧贴海岸移动。输入中的相对坐标需转换为局部索引，便于查找。该算法时间复杂度 $O(1)$，空间 $O(1)$，适用于在线决策。理解方向编码和扫描顺序是解题关键。