不死'火鸟 - 凤翼天翔-' 解题思路与代码实现

拥有了'不死'的能力的藤原妹红，同时获得了操纵火焰的力量，是不死鸟的化身。

不死鸟，和凤凰是同一种生物吗？

题目描述

妹红可以操纵火鸟。火鸟可以看作在边长无限大的棋盘上放置着的一枚棋子 $A$，$A$ 位于 $(x_1,y_1)$ 处。$A$ 以如下规则移动：

• 在奇数次移动时，$A$ 只能向右上或者左下移动一格，如下图红色箭头；
• 在偶数次移动时，$A$ 只能向右下或者左上移动一格，如下图蓝色箭头。

由于棋盘无限大，因此 $x,y$ 的取值可以为负数。

每一步行动时 $A$ 不能待在原地不移动。现在需要把 $A$ 移动到坐标为 $(x_2,y_2)$ 的 $B$ 位置，最少要多少步？特别地，若不存在这样的方案，输出 $-1$。

如下图所示是 $A=(2,7)$，$B=(5,2)$ 的情况。一种移动次数最小的方案已在图上标出，需要 $9$ 步。红色线段表示奇数次的移动，蓝色线段表示偶数次的移动。

输入格式

输入共一行四个整数 $x_1,y_1,x_2,y_2$，描述 $A,B$ 的坐标。

输出格式

输出共一行一个整数。如果存在一条从 $A$ 到 $B$ 的移动方案，输出移动的最小步数；否则输出 $-1$。

样例 #1

样例输入 #1

2 7 5 2

样例输出 #1

9

样例 #2

样例输入 #2

2 2 3 2

样例输出 #2

-1

样例 #3

样例输入 #3

0 0 1000000000 1000000000

样例输出 #3

2000000000

提示

数据范围及约定

对于全部数据，保证 $0\le x_1,y_1,x_2,y_2\le 10^9$。

解题思路

1. 奇偶性判断: 首先判断起点和终点的奇偶性是否相同。因为火鸟的移动规则决定了每一步移动都会改变坐标的奇偶性，如果起点和终点的奇偶性不同，则无法到达。
2. 坐标相同判断: 如果起点和终点坐标相同，则不需要移动，步数为0。
3. 最大移动距离: 定义 $dx = |x_2 - x_1|$，$dy = |y_2 - y_1|$，表示横纵坐标的距离。 $d = max(dx, dy)$ 代表最大移动距离。
4. 判断是否可达: 如果 $d > dx + dy$，则无法到达。例如，如果起点是 $(1, 1)$，终点是 $(4, 2)$，则最大移动距离 $d = 3$，而 $dx + dy = 4$，因此无法到达。
5. 计算最小步数: 如果满足上述条件，则最小步数为 $d$。

代码实现 (C++)

#include <iostream>
using namespace std;

int main() {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;

    // 如果起点和终点的奇偶性不同，则无法到达
    if ((x1 + y1) % 2 != (x2 + y2) % 2) {
        cout << -1 << endl;
        return 0;
    }

    // 如果起点和终点坐标相同，则不需要移动
    if (x1 == x2 && y1 == y2) {
        cout << 0 << endl;
        return 0;
    }

    int dx = abs(x2 - x1);
    int dy = abs(y2 - y1);
    int d = max(dx, dy);  // 移动的最大距离

    // 如果 d > dx + dy，则无法到达
    if (d > dx + dy) {
        cout << -1 << endl;
        return 0;
    }

    cout << d << endl;

    return 0;
}