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)$

根据题意模拟即可，注意方向的变化。

时间复杂度

$O(n)$。

参考文献

C++ 代码

#include <iostream>
using namespace std;

int main() {
    int n, count = 0;
    cin >> n;
    char dir = 'E';
    for (int i = 0; i < n; i++) {
        int cmd;
        cin >> cmd;
        if (cmd == 0) {
            if (dir == 'E') dir = 'S';
            else if (dir == 'S') dir = 'W';
            else if (dir == 'W') dir = 'N';
            else if (dir == 'N') dir = 'E';
        } else if (cmd == 1) {
            if (dir == 'E') dir = 'N';
            else if (dir == 'N') dir = 'W';
            else if (dir == 'W') dir = 'S';
            else if (dir == 'S') dir = 'E';
        } else if (cmd == 2) {
            if (dir == 'E') dir = 'W';
            else if (dir == 'W') dir = 'E';
            else if (dir == 'N') dir = 'S';
            else if (dir == 'S') dir = 'N';
        }
        if (dir == 'N') count++;
    }
    cout << count << endl;
    return 0;
}

算法2

(数学) $O(n)$

blablabla

时间复杂度

参考文献

C++ 代码