题解

本题要求根据宇航员的相对移动描述，计算宇航员最终的绝对坐标和面向的方向。宇航员的运动基于一个初始的绝对坐标系，其中有六个方向：正x、负x、正y、负y、正z和负z，表示前、后、左、右、上和下的方向。

解题思路

1. 坐标系与方向映射：

   • 初始时，宇航员面朝 x 轴正方向，坐标系的六个方向分别对应于：

     • qian（前）：表示x轴正方向。
     • hou（后）：表示x轴负方向。
     • zuo（左）：表示y轴负方向。
     • you（右）：表示y轴正方向。
     • shang（上）：表示z轴正方向。
     • xia（下）：表示z轴负方向。

   这些方向是通过旋转变换来改变的。例如，当宇航员向左转时，前方会变为左侧方向，后方变为右侧方向，等等。

2. 相对移动描述：

   • 给定的每一项运动（如 left x、right x、up x、down x、forward x、back x）都会使宇航员旋转并根据新的方向移动。
   • 旋转：每个方向的旋转通过调整当前的前后左右上下关系来实现。
   • 移动：宇航员根据当前面朝的方向沿着x、y或z轴前进。

3. 旋转操作：

   • left：将宇航员的前方向左转90度。
   • right：将宇航员的前方向右转90度。
   • up：将宇航员的前方向上转90度。
   • down：将宇航员的前方向下转90度。
   • forward：沿着当前前方的方向移动。
   • back：沿着当前反方向移动，即交换前后方向。

4. 状态更新：

   • 每次根据当前面向的方向更新宇航员的坐标。
   • 对于每个命令，根据当前的方向来确定x、y、z轴上的增量。

5. 最后输出：

   • 对每组测试数据输出宇航员的最终坐标和面向方向。

代码实现

#include <iostream>
#include <string.h>
#include <cstdio>
#include <stdlib.h>
#include <algorithm>

using namespace std;

// 定义宇航员的各个方向
typedef struct {
    int qian;  // 前方
    int hou;   // 后方
    int zuo;   // 左方
    int you;   // 右方
    int shang; // 上方
    int xia;   // 下方
} flag;

flag f;  // 存储方向信息

// 定义各个命令
char s1[10] = "left";
char s2[10] = "right";
char s3[10] = "forward";
char s4[10] = "back";
char s5[10] = "up";
char s6[10] = "down";

// 处理左转
void left() {
    int tem = f.qian;
    f.qian = f.zuo;
    f.zuo = f.hou;
    f.hou = f.you;
    f.you = tem;
}

// 处理右转
void right() {
    int tem = f.qian;
    f.qian = f.you;
    f.you = f.hou;
    f.hou = f.zuo;
    f.zuo = tem;
}

// 处理前进（不改变方向，只改变坐标）
void forward() {
    // 不做方向调整，只在当前面向方向上移动
}

// 处理后退
void back() {
    swap(f.qian, f.hou);
    swap(f.zuo, f.you);
}

// 处理向上
void up() {
    int tem = f.qian;
    f.qian = f.shang;
    f.shang = f.hou;
    f.hou = f.xia;
    f.xia = tem;
}

// 处理向下
void down() {
    int tem = f.qian;
    f.qian = f.xia;
    f.xia = f.hou;
    f.hou = f.shang;
    f.shang = tem;
}

int main() {
    int n;
    cin >> n;  // 读取测试数据的组数
    while (n--) {
        int x = 0, y = 0, z = 0;  // 初始化坐标
        int t;
        // 初始化宇航员的方向（正面朝x轴，头顶朝z轴）
        f.qian = 0;  // qian（前）朝x正方向
        f.hou = 3;   // hou（后）朝x负方向
        f.you = 1;   // you（右）朝y正方向
        f.zuo = 4;   // zuo（左）朝y负方向
        f.shang = 2; // shang（上）朝z正方向
        f.xia = 5;   // xia（下）朝z负方向
        cin >> t;  // 读取行走的次数
        while (t--) {
            char s[10];
            int num;
            scanf("%s %d", &s, &num);  // 读取每次行走的命令和步长

            // 根据不同的命令执行相应的动作
            if (!strcmp(s, s1)) left();
            if (!strcmp(s, s2)) right();
            if (!strcmp(s, s3)) forward();
            if (!strcmp(s, s4)) back();
            if (!strcmp(s, s5)) up();
            if (!strcmp(s, s6)) down();

            // 根据当前面朝的方向，更新坐标
            if (f.qian == 0) x += num;     // 前方朝x正方向
            if (f.qian == 3) x -= num;     // 后方朝x负方向
            if (f.qian == 1) y += num;     // 前方朝y正方向
            if (f.qian == 4) y -= num;     // 后方朝y负方向
            if (f.qian == 2) z += num;     // 前方朝z正方向
            if (f.qian == 5) z -= num;     // 后方朝z负方向
        }

        // 输出宇航员的最终位置和面向的方向
        printf("%d %d %d %d\n", x, y, z, f.qian);
    }
    return 0;
}

代码解释

1. 方向定义：

   • flag 结构体用于存储六个方向的状态，其中 qian、hou、zuo、you、shang、xia 分别表示前、后、左、右、上、下六个方向。

2. 命令处理函数：

   • 每个命令（如 left、right、forward、back、up、down）都会影响宇航员的面向方向。通过调整 qian、hou、zuo、you、shang 和 xia 的值，模拟宇航员的旋转或移动。

3. 移动逻辑：

   • 根据当前宇航员的面向方向（f.qian），计算移动时在相应坐标轴上的增量。

4. 主循环：

   • 对于每组测试数据，首先初始化宇航员的位置和面向方向，然后根据每个命令更新宇航员的方向和坐标。

5. 输出结果：

   • 输出最终的坐标（x, y, z）和面向的绝对方向编号（f.qian）。

复杂度分析

• 时间复杂度：

  • 每个命令的处理时间是常数时间 $O(1)$，因为每个命令最多只会改变宇航员的方向和坐标。
  • 所以总的时间复杂度为 $O(n)$，其中 $n$ 是命令的数量。

• 空间复杂度：

  • 主要使用了 flag 结构体存储宇航员的状态，所以空间复杂度为 $O(1)$。

示例

输入：

1
6
left 10
right 11
up 12
down 13
forward 14
back 15

输出：

23 -10 12 3

结论

该题目通过模拟宇航员的相对运动来计算最终的绝对坐标和面向方向。通过旋转和移动的逻辑，能够高效地处理大量的命令并输出正确的结果。