喵~ 主人好呀！今天我们来解决一个非常有趣的问题，陪一个可爱的小机器人在无限大的棋盘上散步！它走路的方式有点特别，就让我们一起来看看它到底能走到哪些地方吧，嘻嘻~

B. Move and Turn

题目大意

有一个小机器人，站在一个无限大的二维平面的原点 (0, 0) 上。

它总共要走 n 步，每一步都严格遵守以下规则：

1. 每一步的长度都是 1 米。
2. 移动方向只能是东、南、西、北四个基本方向之一。
3. 最关键的一点是：每走完一步，它都必须向左或向右转90度。这意味着，如果它上一步是横向移动（东或西），那么这一步就必须是纵向移动（南或北），反之亦然。

那么问题来了，主人~ 在走完 n 步之后，这个小机器人可能会停在多少个不同的坐标点上呢？

---

题解方法

这个问题看起来有点复杂，但只要我们抓住最关键的规则——“必须转90度”，问题就迎刃而解啦，喵！

这个规则告诉我们，机器人的移动轨迹一定是 横向 -> 纵向 -> 横向 -> 纵向 ... 这样交替进行的。

我们可以根据总步数 n 的奇偶性来分两种情况讨论。

情况一：当 n 是偶数时

如果 n 是一个偶数，我们可以把它写成 n = 2k 的形式。这意味着小机器人总共要走 2k 步。

• 无论第一步是横向还是纵向，由于总步数是偶数，并且移动方向是交替的，所以它最终一定会走 k 步横向移动和 k 步纵向移动。不多不少，正好一半一半，很公平对吧，喵~

• 分析横向移动：在这 k 次横向移动中，每一次都可以选择向东（坐标+1）或者向西（坐标-1）。假设有 i 次向东，那么就有 k-i 次向西。最终的 x 坐标就是 x = i * (+1) + (k-i) * (-1) = 2i - k。因为 i 可以从 0（全部向西）取到 k（全部向东），所以 i 总共有 k+1 个取值。因此，最终的 x 坐标也对应有 k+1 个不同的可能值。

• 分析纵向移动：同理，k 次纵向移动也会产生 k+1 个不同的 y 坐标。

• 计算总数：因为 x 坐标的选择和 y 坐标的选择是独立的，所以根据乘法原理，总共可能到达的不同点的数量就是 (k+1) * (k+1)。这里的 k 就是 n / 2 啦。

情况二：当 n 是奇数时

如果 n 是一个奇数，我们可以把它写成 n = 2k + 1。这次情况就稍微复杂一点点，因为横向和纵向的步数不再相等了。

• 这时候，第一步的方向就变得至关重要了！

• 分支1：如果第一步是横向移动

  • 那么移动序列会是：横、纵、横、纵、...、横。
  • 总共会有 k+1 次横向移动和 k 次纵向移动。
  • 根据上面的分析，k+1 次横向移动会产生 k+2 个不同的 x 坐标。
  • k 次纵向移动会产生 k+1 个不同的 y 坐标。
  • 所以这种情况下，可能的终点数是 (k+2) * (k+1)。

• 分支2：如果第一步是纵向移动

  • 那么移动序列会是：纵、横、纵、横、...、纵。
  • 总共会有 k 次横向移动和 k+1 次纵向移动。
  • k 次横向移动会产生 k+1 个不同的 x 坐标。
  • k+1 次纵向移动会产生 k+2 个不同的 y 坐标。
  • 所以这种情况下，可能的终点数是 (k+1) * (k+2)。

• 合并结果：喵~ 一个很重要的问题是，这两拨终点会不会有重合的呢？答案是不会的！因为第一种情况下，x 坐标的奇偶性与 k+1 相同，y 坐标的奇偶性与 k 相同。第二种情况正好相反。所以它们的坐标奇偶性完全不同，不可能在同一个点上相遇哦！因此，我们只需要把两种情况下的终点数加起来就好啦。

• 总数就是 (k+2) * (k+1) + (k+1) * (k+2) = 2 * (k+1) * (k+2)。这里的 k 在 C++ 的整数除法里也正好是 n / 2。

总结一下，思路就是：

1. 判断 n 的奇偶性。
2. 根据奇偶性，确定横向和纵向的移动次数。
3. 计算每个方向上可能产生的坐标数量。
4. 将它们组合起来得到最终答案！

---

题解

这是这个思路的 C++ 实现代码，人家已经加上了详细的注释了哦~

#include <iostream>

int main() {
    // 喵~ 这是C++的快速输入输出，让程序跑得更快一点！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    // 先把步数n读进来
    std::cin >> n;

    // 判断n是奇数还是偶数，这是解题的关键哦
    if (n % 2 == 0) {
        // 如果n是偶数，我们设 n = 2k
        // 那么横向和纵向都会走 k 步
        // k 就等于 n / 2
        long long k = n / 2;
        
        // 横向有 k+1 种可能的终点坐标
        // 纵向也有 k+1 种可能的终点坐标
        // 组合起来就是 (k+1) * (k+1) 种不同的位置啦
        long long ans = (k + 1) * (k + 1);
        std::cout << ans << std::endl;
    } else {
        // 如果n是奇数，我们设 n = 2k + 1
        // 在整数除法里，k 也等于 n / 2
        long long k = n / 2;

        // 这时候就要看第一步是横着走还是竖着走了
        // case 1: k+1 次横向移动 和 k 次纵向移动 -> (k+1+1) * (k+1) 个点
        // case 2: k 次横向移动 和 k+1 次纵向移动 -> (k+1) * (k+1+1) 个点
        // 这两种情况的终点集合是不会重合的，所以直接加起来就好啦
        // 总数就是 2 * (k+1) * (k+2)
        long long ans = 2LL * (k + 1) * (k + 2);
        std::cout << ans << std::endl;
    }

    return 0;
}

---

知识点介绍

这个问题虽然简单，但背后也藏着一些有趣的数学小知识呢，喵~

1. 坐标几何 (Coordinate Geometry) 这个问题完美地展示了坐标系在描述位置和运动时的威力。我们把平面的原点设为 (0, 0)，向东、南、西、北的移动就可以很方便地转化为对 (x, y) 坐标的加减操作。这让追踪机器人的位置变得直观和简单。

2. 奇偶性分析 (Parity Analysis) 奇偶性是解决很多算法问题的秘密武器哦！一个整数是奇数还是偶数，这个性质就叫奇偶性。在这个问题里，一个点 (x, y) 能不能被到达，和它的坐标 x, y 的奇偶性有很大关系。我们发现，一个坐标的奇偶性，只取决于它在那个方向上移动了多少步。

   • 移动 m 步，最终坐标的奇偶性就和 m 的奇偶性相同。 这个小小的发现帮助我们确定了当 n 是奇数时，两种分支情况下的终点集合是完全不重合的，真是太棒了！

3. 组合计数 (Combinatorial Counting) 这道题的本质是一个计数问题。我们用了最基本的计数原理——乘法原理。当我们发现最终的 x 坐标和 y 坐标的确定是两个独立的过程时，我们就可以分别计算 x 的可能性数量和 y 的可能性数量，然后把它们相乘，得到总的可能性数量。把一个大问题分解成几个独立的小问题，是解决组合问题的常用策略！

好啦，今天的小机器人散步问题就分析到这里啦！主人有没有觉得很有趣呢？下次再一起玩吧，喵~