题目描述

在一个拥有无限大小的二维平面的原点处，有一个舞蹈机器人，这个机器人将在这个平面上跳舞。

这个机器人每次可以向自己的前方移动一个单位的长度，由于它需要在移动的过程中跳舞，因此，舞蹈机器人每移动一次，就必须向左或右方向旋转 ，即如果此次机器人往上或下方向进行了一次移动，那么，下一次就只能往左或右方向进行一次移动。最开始时，它可以选择上下左右四个方向中的任意一个作为初始方向。

现在，机器人根据上述规则一共移动了 步，请问，机器人最终可以到达多少个不同的终点？机器人到达终点时的方向可以忽略。

输入格式

输入共一行，包含一个整数 ，表示机器人总共移动的步数。

输出格式

输出共一行，包含一个整数，表示机器人最终能够到达的不同终点的个数。

样例 1 输入

1

样例 1 输出

4

样例 1 解释

因为总共只移动了一次，则有上下左右四个方向的四个答案。

样例 2 输入

2

样例 2 输出

4

样例 2 解释

因为总共会移动两次，且第二次的方向必须向左或向右旋转 ，因此，最终能到的终点只有原点左上、右上、左下、右下四个与原点距离为 的点。

样例 3 输入

3

样例 3 输出

12

样例 4 输入

597

样例 4 输出

179400

【题目分析】

（1）分析：

• 机器人从原点 (0,0) 出发。

• 初始方向可以是上、下、左、右任意一个。

• 移动规则：
  
  如果上一步是 上下 方向移动，下一步必须是 左右 方向移动；
  
  如果上一步是 左右 方向移动，下一步必须是 上下 方向移动。

• 问：走完 n 步后，能到达多少个不同的终点（位置不同即可，方向无关）。

（2）数据推导一下

n = 1

可以往 4 个方向走一步，终点有：

(0,1), (0,-1), (1,0), (-1,0)

共 4 个。

n = 2

第一步：上下左右 4 种

第二步：必须转 90°。

例如：

• 第一步向上到 (0,1)，第二步只能向左或向右 → ( -1,1) 或 (1,1)

• 第一步向下到 (0,-1)，第二步 → (-1,-1) 或 (1,-1)

• 第一步向左到 (-1,0)，第二步 → (-1,1) 或 (-1,-1)

• 第一步向右到 (1,0)，第二步 → (1,1) 或 (1,-1)

所有终点：

(1,1), (1,-1), (-1,1), (-1,-1)

共 4 个。

n = 3

我们枚举一下可能的终点（可以手推或画图）：

第一步：4 种

第二步：2 种

第三步：2 种

路径数 = 4 * 2^  (n-1) 条路径，但不同路径可能到同一个点。

通过枚举（或对称性）可得： n=3 时，终点有：

• 距离原点 1 的点：如 (0,1), (1,0) 等，共 4 个

• 距离原点 √5 的点：如 (2,1), (1,2) 等，共 8 个

总共 12 个。

(3)规律

通过观察 n=1,2,3,4 的结果（可以自己算 n=4 是 25 个点），发现：

• n 为偶数时，终点数 = $(n\mathrm{/}2+1{)}^2$
  
  验证：n=2 → (1+1)^2=4，n=4 → (2+1)^2=9

• n 为奇数时，终点数 = $(1+(n+1)\mathrm{/}2)\times (n+1)$
  
  验证：n=1 → (1+1)×2=4，n=3 → (1+2)×4=12

（4）原因

偶数情况：

n 为偶数时，机器人在水平和垂直方向上的步数相等（各 n/2 步），但顺序交错。

最终位置 = (水平位移, 垂直位移)，其中水平位移 = 向右步数 - 向左步数，垂直位移 = 向上步数 - 向下步数。

设水平方向净步数 x，垂直方向净步数 y，则 |x|+|y| ≤ n 且 x 与 y 同奇偶（因为每两步才能同时改变两个坐标）。

实际上偶数步结束时，x 与 y 必须同为偶数（因为 n/2 步水平，n/2 步垂直，每方向净位移是整数且同奇偶）。

最终可推出可能的位置是网格上所有满足 |x|+|y| ≤ n 且 x ≡ y (取余 2) 的点。

这个数量 = $(n\mathrm{/}2+1{)}^2$（n/2  + 1）^2  （可通过画菱形格点验证）。

奇数情况：

n 为奇数时，一个方向比另一个方向多 1 步。

最终位置满足 |x|+|y| ≤ n 且 x 与 y 奇偶性不同。

数量 = $(1+(n+1)\mathrm{/}2)\times (n+1)$ $(1+(n+1)\mathrm{/}2)\times (n+1)$

$(5)\; 是否允许走回头路$

规则只限制了相邻两步必须垂直（上一步是上下方向，下一步必须是左右方向；上一步是左右方向，下一步必须是上下方向）。

并没有禁止回到之前的位置，也没有禁止“原路返回”这种操作。

例如 n=4 时可以回到原点：

1. 上 (0,1)

2. 左 (-1,1)

3. 下 (-1,0)

4. 右 (0,0)

• 允许走回头路。

• 终点只统计不同的坐标，不关心路径是否重复经过某点。

•   可以走回头路，不影响最终能到达的位置集合。

【参考代码】

#include <cstdio>  #include <iostream>  using namespace std;  int main() {      int n;      cin >> n;      if(n%2==1) cout<<(1 + (n + 1) / 2) * (n + 1)<<endl;      else cout<<(n / 2 + 1) * (n / 2 + 1)<<endl;      return 0;  }