C++ 算法题：转向游戏II - 方向感测试 - 解题思路与代码

转向游戏II - 方向感测试

题目描述

小明自认为方向感很好，请小红来测试。小红先让小明面对'东'方立正站好，然后发出 '向左转'、'向右转' 或 '向后转' 的命令。每个命令执行后，小明都正确地说出了他面对的方向。 命令是以数字方式表达：$0$ 代表 '向右转'，$1$ 代表 '向左转'，$2$ 代表 '向后转'。

输入格式

从标准输入读入数据。 输入共两行。第一行是一个正整数 $n$（$1\le n\le 10,000$），代表命令的条数；第二行是 $n$ 个整数，每个整数是 $0$、$1$ 或 $2$，代表小红发出的口令。

输出格式

输出到标准输出。 一个整数，代表小明回答 '北' 的次数。

样例 #1

样例输入 #1

5
0 1 0 0 1

样例输出 #1

0

提示

子任务

对于 $30%$ 的数据，$n\le10$； 对于 $50%$ 的数据，$n\le100$； 对于 $70%$ 的数据，$n\le1,000$； 对于 $100%$ 的数据，$n\le10,000$。 特别地，对于其中 $20%$ 的数据，小红发出的命令仅有一种。

算法1

(模拟) $O(n)$

根据题目描述，我们可以列出一个表格，表示小明转向后面的方向。其中，$0$ 表示向右转，$1$ 表示向左转，$2$ 表示向后转。

当前方向 | 向左转 | 向右转 | 向后转 ---|---|---|---| 北 | 3 | 1 | 2 东 | 0 | 2 | 3 南 | 1 | 3 | 0 西 | 2 | 0 | 1

我们可以用一个变量 $d$ 表示小明面对的方向，初始值为 $1$，即表示小明面对东方。

然后，我们依次处理每个命令，根据表格更新 $d$ 的值。最后，统计小明回答北的次数，即可得到答案。

时间复杂度

总共需要处理 $n$ 个命令，每个命令需要 $O(1)$ 的时间更新 $d$ 的值，因此总时间复杂度为 $O(n)$。

C++ 代码

#include <iostream>
using namespace std;

int main() {
    int n, cmd, d = 1, north = 0;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> cmd;
        switch (cmd) {
            case 0:  // 向右转
                d = (d + 1) % 4;
                break;
            case 1:  // 向左转
                d = (d + 3) % 4;
                break;
            case 2:  // 向后转
                d = (d + 2) % 4;
                break;
        }
        if (d == 0) {
            north++;
        }
    }
    cout << north << endl;
    return 0;
}

算法2

(模拟) $O(n)$

其实，我们可以用一个数组 $dir$ 来表示表格中的内容。其中，$dir[i][j]$ 表示当前面对 $i$ 方向，执行命令 $j$ 后的方向。这样，我们就可以用一个变量 $d$ 表示小明面对的方向，初始值为 $1$，即表示小明面对东方。然后，我们依次处理每个命令，根据 $dir[d][cmd]$ 更新 $d$ 的值。最后，统计小明回答北的次数，即可得到答案。

时间复杂度

总共需要处理 $n$ 个命令，每个命令需要 $O(1)$ 的时间更新 $d$ 的值，因此总时间复杂度为 $O(n)$。

C++ 代码

#include <iostream>
using namespace std;

int main() {
    int n, cmd, d = 1, north = 0;
    int dir[4][3] = {
        {3, 1, 2},
        {0, 2, 3},
        {1, 3, 0},
        {2, 0, 1}
    };
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> cmd;
        d = dir[d][cmd];
        if (d == 0) {
            north++;
        }
    }
    cout << north << endl;
    return 0;
}