lanqiao/寻宝.c

// 【问题描述】
// 小蓝正在玩一个寻宝游戏。寻宝游戏在一个方格图上进行。方格图中的每一个格子都有一个坐标 (r, c)，其中越往北 r 越小，越往南 r 越大，越往东 c 越大，越往西 c 越小。南北相邻方格的 c 坐标相同，r 坐标差一。东西相邻方格的 r 坐标相同， c 坐标差一。

// 游戏开始时，小蓝站在 (0, 0) 处，面向北边。游戏区域无限大，且没有障碍。每一步，小蓝控制自己的角色走一步，他可以有如下三种选择：

// 向前走：朝现在的方向前进到相邻的方格中，并保持当前的方向。
// 向左走：向左转90度，并前进到相邻的方格中（即进入到原来左边的方格），面向的方向变为了原来的左边。
// 向右走：向右转90度，并前进到相邻的方格中（即进入到原来右边的方格），面向的方向变为了原来的右边。
// 小蓝玩了一会儿，一共走了 n 步，他记录了自己的每一个动作。但是他没有找到宝藏。他怀疑前面的某一步出现了失误。他想知道，如果他改变之前的某一步，能到的位置有哪些。由于这个太复杂，他想知道最终到的位置（第 n 步后到的位置）有多少种。

// 【输入格式】
// 输入的第一行包含一个整数 n ，表示小蓝走了 n 步。

// 第二行包含一个长度为 n 的由大写字母组成的字符串，依次表示小蓝走的每一步。字母 F 、 L 、 R 分别表示对应的步是向前走、向左走、向右走。

// 【输出格式】
// 输出一行，包含一个整数，表示如果改变某一步，可以到的位置的种类数。

// 【样例输入】
// 3
// FLR
// 【样例输出】
// 6
// 【样例说明】
// 如果不改变，三步依次走到：(-1, 0), (-1, -1), (-2, -1) ，最终位置为 (-2, -1) 。

// 如果第一步改成 L，三步依次走到：(0, -1), (1, -1), (1, -2) ，最终位置为 (1, -2) 。

// 如果第一步改成 R，三步依次走到：(0, 1), (-1, 1), (-1, 2) ，最终位置为 (-1, 2) 。

// 如果第二步改成 F，三步依次走到：(-1, 0), (-2, 0), (-2, 1) ，最终位置为 (-2, 1) 。

// 如果第二步改成 R，三步依次走到：(-1, 0), (-1, 1), (0, 1) ，最终位置为 (0, 1) 。

// 如果第三步改成 F，三步依次走到：(-1, 0), (-1, -1), (-1, -2) ，最终位置为 (-1, -2) 。

// 如果第三步改成 L，三步依次走到：(-1, 0), (-1, -1), (0, -1) ，最终位置为 (0, -1) 。

// 共有 6 种不同的最终位置。

// 【样例输入】
// 4
// RRRR
// 【样例输出】
// 6
// 【样例说明】
// 有 8 种改变方法：

// 改为 FRRR ，最终位置为 (0, 0)；

// 改为 LRRR ，最终位置为 (0, 0)；

// 改为 RFRR ，最终位置为 (1, 1)；

// 改为 RLRR ，最终位置为 (0, 2)；

// 改为 RRFR ，最终位置为 (2, 0)；

// 改为 RRLR ，最终位置为 (2, 2)；

// 改为 RRRF ，最终位置为 (1, -1)；

// 改为 RRRL ，最终位置为 (2, 0)。

// 不同的最终位置共有 6 种。

// 【评测用例规模与约定】
// 对于 30% 的评测用例，1 <= n <= 20。

// 对于 60% 的评测用例，1 <= n <= 1000。

// 对于所有评测用例，1 <= n <= 100000

#include <stdio.h>
#include <stdlib.h>

#define MAXN 100000

int n;
char actions[MAXN + 1];
int original_dir[MAXN + 1];
int original_pos_x[MAXN + 1];
int original_pos_y[MAXN + 1];

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

void simulate(int step, int new_action, int *final_x, int *final_y) {
    int dir = original_dir[step];
    int x = original_pos_x[step];
    int y = original_pos_y[step];

    if (new_action == 'F') {
        // 前进，方向不变
    } else if (new_action == 'L') {
        // 向左转，方向减一
        dir = (dir - 1 + 4) % 4;
    } else if (new_action == 'R') {
        // 向右转，方向加一
        dir = (dir + 1) % 4;
    }

    // 执行新的动作
    x += dx[dir];
    y += dy[dir];

    // 继续模拟后续步骤
    for (int i = step + 1; i < n; i++) {
        char action = actions[i];
        if (action == 'F') {
            // 前进，方向不变
        } else if (action == 'L') {
            // 向左转，方向减一
            dir = (dir - 1 + 4) % 4;
        } else if (action == 'R') {
            // 向右转，方向加一
            dir = (dir + 1) % 4;
        }
        x += dx[dir];
        y += dy[dir];
    }

    *final_x = x;
    *final_y = y;
}

int main() {
    scanf("%d", &n);
    scanf("%s", actions);

    // 初始化原始方向和位置
    original_dir[0] = 0;
    original_pos_x[0] = 0;
    original_pos_y[0] = 0;

    // 预计算原始方向和位置序列
    for (int i = 0; i < n; i++) {
        char action = actions[i];
        int dir = original_dir[i];
        int x = original_pos_x[i];
        int y = original_pos_y[i];

        if (action == 'F') {
            // 前进，方向不变
        } else if (action == 'L') {
            // 向左转，方向减一
            dir = (dir - 1 + 4) % 4;
        } else if (action == 'R') {
            // 向右转，方向加一
            dir = (dir + 1) % 4;
        }

        // 更新位置
        x += dx[dir];
        y += dy[dir];

        original_dir[i + 1] = dir;
        original_pos_x[i + 1] = x;
        original_pos_y[i + 1] = y;
    }

    // 使用哈希表存储最终位置
    int hash[200001][2];
    int hash_size = 0;

    for (int i = 0; i < n; i++) {
        char original_action = actions[i];
        // 可能的动作变化
        char possible_actions[2];
        if (original_action == 'F') {
            possible_actions[0] = 'L';
            possible_actions[1] = 'R';
        } else if (original_action == 'L') {
            possible_actions[0] = 'F';
            possible_actions[1] = 'R';
        } else if (original_action == 'R') {
            possible_actions[0] = 'F';
            possible_actions[1] = 'L';
        }

        for (int j = 0; j < 2; j++) {
            char new_action = possible_actions[j];
            int final_x, final_y;
            simulate(i, new_action, &final_x, &final_y);

            // 检查是否已存在该位置
            int found = 0;
            for (int k = 0; k < hash_size; k++) {
                if (hash[k][0] == final_x && hash[k][1] == final_y) {
                    found = 1;
                    break;
                }
            }
            if (!found) {
                hash[hash_size][0] = final_x;
                hash[hash_size][1] = final_y;
                hash_size++;
            }
        }
    }

    printf("%d\n", hash_size);

    return 0;
}