P5380 鸭棋 题解

· · 题解

P5380 鸭棋 题解

题意简述

一款在中国象棋基础上制作的游戏“鸭棋”，把棋子“炮”替换为了“鸭”。其中，“鸭”的移动规则是沿着 2\times 3 网格的对角线上移动，但是如果在如图的两个红点处有其他棋子，则会“别鸭腿”，移动失败。

接下来，给出 Q 次移动的起点 \left(x_1, y_1\right) 和终点 \left(x_2, y_2\right)，对于每一个步骤，要求求出：

如果不合法，输出 Invalid command。

其中，“不合法”的情况包括：

一方的王（将帅）被吃掉则游戏结束，一步之内可以使游戏结束被称为“将军”。特别地，王被吃掉的那一轮不能算作将军。

题目分析

本题数据范围很小，按照题意模拟即可。主要包括以下步骤：

这篇题解将会在判断合法性时采用较为新颖的方法，可以优化编码体验。同时，也会带有一定的面向对象编程的思想。对于模拟题，我的代码通常以追求可读性为主。

接下来按照我会大致按照自己的编码顺序，从大体框架开始介绍。

大体框架

对于棋盘的存储，我选择了直接存储所有棋子及其位置信息。

考虑把棋子抽象成一个类。那么，它需要包括三个属性：类型，位置和队伍。进一步，位置包含 x 坐标和 y 坐标两个属性。我们用一个二维向量表示位置。之所以叫做向量，是因为我们接下来会用到一部分的向量运算。

接下来就可以一层一层地定义了。向量类：

struct Vec2d {
    int x, y;
    Vec2d operator+(const Vec2d &other) const { return {x+other.x, y+other.y}; } // 加
    Vec2d operator-(const Vec2d &other) const { return {x-other.x, y-other.y}; } // 减
    Vec2d operator*(const int other) const { return {x*other, y*other}; } // 数乘
    Vec2d operator/(const int other) const { return {x/other, y/other}; } // 乘以 1/other
    int operator*(const Vec2d &other) const { return x*other.x + y*other.y; } // 数量积
    int cross(const Vec2d &other) const { return x*other.y - y*other.x; } // 叉乘的模长
    bool operator==(const Vec2d &other) const { return x==other.x and y==other.y; } // 相等
    bool operator!=(const Vec2d &other) const { return x!=other.x or y!=other.y; } // 不等

    int sqrDistance(const Vec2d &other) const { // 两点间欧几里得距离的平方
        return (x-other.x)*(x-other.x)+(y-other.y)*(y-other.y); 
    }
    int manhattan(const Vec2d &other) const { return abs(x-other.x)+abs(y-other.y); } // 曼哈顿距离
    int chebyshev(const Vec2d &other) const { return std::max(abs(x-other.x), abs(y-other.y)); } // 切比雪夫距离

    int sqrAbs() const { return x*x+y*y; }  // 模长的平方
};

这里，我们实现了两点间的三种距离也是为下文做准备。叉乘的结果是一个三维向量，这里为了方便直接返回模长。对于欧几里得距离（和模长），我们省略了开平方操作（这会引入浮点数的误差），直接采用开方前的结果。

阵营枚举：

enum Team {
    Red,
    Blue,
};

按照定义顺序，Team::Red 和 Team::Blue 分别为 0 和 1。所以我们可以直接使用“异或”操作进行阵营的轮换。

接下来我们定义棋子类和棋子列表。

struct Piece;  // 预先声明，解决循环引用问题
vector<Piece> pieces;

struct Piece {
    string  name;   // 棋子类型，如 horse, elephant
    Vec2d   pos;    // 棋子位置
    Team    team;   // 棋子阵营

    bool reachable(Vec2d dest) {  // 能否到达目标地点
        // To be done.
    }
};

这里有一个小问题，后面我们在实现 reachable 方法的时候会用到 pieces 数组，所以采用了预先声明的办法解决循环引用问题。当然，也可以在类外定义 reachable 方法。

绝大多数定义在这一步就完成了。

判断合法性

我们先不考虑其他因素，只处理两点的位置和“别脚”问题。

对于相对位置，我们使用上文的三种距离筛选。我们先简要介绍一下这三种距离。

对于两个点 \left(x_1, y_1\right) 和 \left(x_2, y_2\right)，我们令 \Delta x=\lvert x_1-x_2 \rvert, \Delta y=\lvert y_1-y_2 \rvert。则两点的欧几里得距离是 \Delta x^2+\Delta y^2，曼哈顿距离是 \Delta x+\Delta y，切比雪夫距离是 \max{\left\{\Delta x, \Delta y\right\}}。

感性地理解，曼哈顿距离下的“圆”是一个斜着的正方形，切比雪夫距离下的“圆”是一个正置的正方形。

接下来，我们用 d 表示欧几里得距离，m 表示曼哈顿距离，c 表示切比雪夫距离。各种棋子便有如下的筛法：

接下来处理“别脚”的情况。这里我们就用到向量筛选。我们设 Q 是当前棋盘上的一个棋子，出发点是 O，终点是 P。为了简便，令 \vec{a}=\overrightarrow{OP}, \vec{b}=\overrightarrow{OQ}。

对于象，不难发现 2\vec{b}=\vec{a} 会构成压象眼。

接下来考虑别马脚。注意到，别马脚的子距离起点长度一定为 1，即 \lvert \vec{b} \rvert=1。此外，我们注意到，这两条向量的夹角永远是不变的，同时模长不变，自然想到利用数量积筛选。做 \vec{b} 在 \vec{a} 上的投影，显然有 \vec{a}\cdot\vec{b}=2。我们也可以用 GeoGebra 的画图功能来验证这个筛选。

红色直线上的点符合数量积要求，蓝色圆上的点符合模长要求，同时由于两个轴上的坐标都是整数，所以点 Q 是唯一的——这个点也确实会别到马脚。

对于鸭子，有了处理别马脚的经验，也能很快的想出结论。第一种可能，\lvert \vec{b} \rvert=1 且 \vec{a}\cdot\vec{b}=3；第二种可能，\lvert \vec{b} \rvert=\sqrt{5} 且 \vec{a}\cdot\vec{b}=8。

对于车，要求中间没有挡道的棋子。不难想到，如果一个棋子要“挡道”，需要符合以下条件：

使用向量运算描述一下，即为以下条件：

\begin{cases} \vec{a}\times\vec{b}=\vec0 \\ \vec{a}\cdot\vec{b}>0 \\ \lvert \vec{b} \rvert<\lvert \vec{a} \rvert \end{cases}

最后，再检测一下落点是否在棋盘上，以及是否在攻击己方棋子就可以了。

代码如下：

struct Piece {
    // ...
    // 检查是否可以到达目标位置，但是只对位置进行判断
    bool reachable_pos(Vec2d dest) {
        if (name == "captain") {
            return pos.sqrDistance(dest) == 1;
        } else if (name == "guard") {
            return pos.manhattan(dest) == 2 and pos.chebyshev(dest) == 1;
        } else if (name == "elephant") {
            return pos.manhattan(dest) == 4 and pos.chebyshev(dest) == 2 and 
                not pieces.some(lambda(p, (p.pos-pos)*2==(dest-pos))); 
        } else if (name == "horse") {
            return pos.sqrDistance(dest) == 5 and 
                not pieces.some(lambda(p, 
                    p.pos.sqrDistance(pos) == 1 and (p.pos-pos)*(dest-pos)==2));
        } else if (name == "car") {
            auto a = dest-pos;
            return pos.chebyshev(dest) == pos.manhattan(dest) and not pieces.some([&](auto p) {
                auto b = p.pos-pos;
                return b.cross(a)==0 and b.sqrAbs()<a.sqrAbs() and b*a>0;
            });
        } else if (name == "soldier") {
            return pos.chebyshev(dest) == 1;
        } else {  // duck
            auto a = dest-pos;
            return pos.sqrDistance(dest) == 13 and not pieces.some([&](auto p) {
                auto b = p.pos-pos;
                return (a*b==8 and b.sqrAbs()==5) or (a*b==3 and b.sqrAbs()==1);
            });
        }
    }

    bool reachable(Vec2d dest) {  // 能否到达目标地点
        return 0<=dest.x and dest.x<_X and
            0<=dest.y and dest.y<_Y and
            reachable_pos(dest) and 
            not pieces.some(lambda(p, p.pos==dest and p.team==team));
    }
}

这里为了方便，我继承了 std::vector，即代码中的 vector，并添加了 some(func) 方法，用于判断是否存在任意一个元素 i，使得 func(i) 返回真。

template <typename T> struct vector: public std::vector<T> {
    template <class Func>
    bool some(const Func&& f) {
        for (auto& i: *this) {
            if (f(i))  return true;
        }
        return false;
    }
};

而 lambda 是一个宏，定义如下：

#define lambda(arg, expr) [&](auto arg){return expr;}

其他流程

这里就不多加阐述了，可以见代码注释

void solve() {
    init();
    // 双方的王
    Piece& kingRed = pieces[0];
    Piece& kingBlue = pieces[1];

    bool round = 0;
    bool gameOver = false;
    from(_, 1, Q) {
        if (gameOver) {  // 游戏结束一定不合法
            cout << "Invalid command\n";
            continue;
        }
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        auto src = Vec2d{x1, y1};  // 起点
        auto dest = Vec2d{x2, y2};  // 终点

        auto selected = std::find_if(pieces.begin(), pieces.end(), 
            lambda(p, p.pos==src and p.team==round));  // 筛选，要求位置一致并且阵营正确
        if (selected == pieces.end()) {  // 没找到
            cout << "Invalid command\n";
            continue;
        }

        bool available = selected->reachable(dest);  // 判断终点位置是否可达
        if (not available) {
            cout << "Invalid command\n"; continue;
        }
        // 主语
        cout << (selected->team==Team::Red? "red ": "blue ") << selected->name << ';';

        // 宾语
        bool isKingKilled = false;  // 王被击杀，判断游戏结束
        auto attackedIter = std::find_if(pieces.begin(), pieces.end(), lambda(p, p.pos==dest));
        selected->pos = dest;
        if (attackedIter == pieces.end()) {
            cout << "NA;";  // 移到空格子
        } else {
            isKingKilled = (attackedIter->name=="captain");  // 游戏结束
            // 输出宾语
            cout << (attackedIter->team==Team::Red? "red ": "blue ") << attackedIter->name << ';';
            pieces.erase(attackedIter);  // 移除被吃的子
        }
        bool isKingInDanger = false;  // 被将军
        isKingInDanger &= !isKingKilled;  // 特判，王已经死了
        isKingInDanger |= pieces.some(lambda(p, p.reachable(kingRed.pos) and p.team==Team::Blue));
        isKingInDanger |= pieces.some(lambda(p, p.reachable(kingBlue.pos) and p.team==Team::Red));
        cout << (isKingInDanger? "yes;": "no;") << (isKingKilled? "yes": "no") << '\n';
        gameOver |= isKingKilled; 
        round ^= 1;  // 当且仅当操作合法，进行轮换
    }
}

初始化

初始化主要用于处理棋子的初始位置。

我采用了一些宏定义简化代码。宏定义有时可以减少枯燥乏味的代码，不过也要慎用，避免出现一些很难调的 bug。

int Q;
void init() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    // 添加一个子
    #define add(name,px,py,team) pieces.push_back(Piece{name, {px, py}, Team::team});
    // 添加四个中心对称的子
    #define four(name,dx,dy) add(name,4-dx,4+dy,Red) add(name,4-dx,4-dy,Red) \
        add(name,5+dx,4-dy,Blue) add(name,5+dx,4+dy,Blue)
    // 添加底线上的一个子
    #define bottom(name,dy) four(name,4,dy);
    add("captain",0,4,Red) add("captain",9,4,Blue)
    bottom("car",4)bottom("horse",3)bottom("elephant",2)bottom("guard",1)
    four("duck",2,4)
    four("soldier",1,4)four("soldier",1,2)add("soldier",3,4,Red)add("soldier",6,4,Blue)
    cin >> Q;
}

那么这个代码就完成了。

警示后人

在写这个代码时，我被一个引用造成的 bug 卡了四个小时，原因是我在引用了 vector 上的一个元素之后，删除了另一个元素，导致内存上这个位置发生了变化，于是这个引用指向了其他元素。引用其实也是指向一个内存上的地址，和指针一样，所以不要掉以轻心，尤其是对可变容器中一个对象的引用，更要万分小心。（例如，vector.push_back 看上去人畜无害，但是如果触发了扩容，这个 vector 上的所有引用都会失效）

总结

本文中，我们采用了一些数学方法转换和简化了检查棋子的过程，感觉思路比较新颖，希望管理能够通过。

模拟题最重要的是对于题意的理解和保持思路的清晰。不过，这么长的代码，如果出现 bug，调起来还是很头疼的，所以还是要细心一些，并且记录一些平时遇到的 bug，在以后的代码中也多注意这些问题。

在文化课中学习向量时，我有时想，“这么抽象的东西到底有什么用”，直到编写这份代码的时候，我鬼使神差地给两个位置做了减法——这就是向量。于是，那些尘封在课本中的知识涌入脑海，前文的那些步骤也很自然了。把这些冗长的规则，都转变成了一个个简短的式子，也许这就是数学的魅力吧。

不知不觉也写了不少了，感谢您的观看。

完整代码

/**
 * @link https://www.luogu.com.cn/problem/P5380
 */

#include <bits/stdc++.h>
#define from(i,b,e) for(int i=(b);i<=(e);i++)
#define lambda(arg, expr) [&](auto arg){return expr;}

using std::string, std::cin, std::cout;

template <typename T> struct vector: public std::vector<T> {
    template <class Func>
    bool some(const Func&& f) {
        for (auto& i: *this) {
            if (f(i))  return true;
        }
        return false;
    }
};

const int _X = 10;
const int _Y = 9;

struct Vec2d {
    int x, y;
    Vec2d operator+(const Vec2d &other) const { return {x+other.x, y+other.y}; } // 加
    Vec2d operator-(const Vec2d &other) const { return {x-other.x, y-other.y}; } // 减
    Vec2d operator*(const int other) const { return {x*other, y*other}; } // 数乘
    Vec2d operator/(const int other) const { return {x/other, y/other}; } // 乘以 1/other
    int operator*(const Vec2d &other) const { return x*other.x + y*other.y; } // 数量积
    int cross(const Vec2d &other) const { return x*other.y - y*other.x; } // 叉乘的模长
    bool operator==(const Vec2d &other) const { return x==other.x and y==other.y; } // 相等
    bool operator!=(const Vec2d &other) const { return x!=other.x or y!=other.y; } // 不等

    int sqrDistance(const Vec2d &other) const { // 两点间欧几里得距离的平方
        return (x-other.x)*(x-other.x)+(y-other.y)*(y-other.y); 
    }
    int manhattan(const Vec2d &other) const { return abs(x-other.x)+abs(y-other.y); } // 曼哈顿距离
    int chebyshev(const Vec2d &other) const { return std::max(abs(x-other.x), abs(y-other.y)); } // 切比雪夫距离

    int sqrAbs() const { return x*x+y*y; } // 模长的平方
};

enum Team {
    Red,
    Blue,
};

struct Piece;  // 预先声明，解决循环引用问题
vector<Piece> pieces;

struct Piece {
    string  name;   // 棋子类型，如 horse, elephant
    Vec2d   pos;    // 棋子位置
    Team    team;   // 棋子阵营

    // 检查是否可以到达目标位置，但是只对位置进行判断
    bool reachable_pos(Vec2d dest) {
        if (name == "captain") {
            return pos.sqrDistance(dest) == 1;
        } else if (name == "guard") {
            return pos.manhattan(dest) == 2 and pos.chebyshev(dest) == 1;
        } else if (name == "elephant") {
            return pos.manhattan(dest) == 4 and pos.chebyshev(dest) == 2 and 
                not pieces.some(lambda(p, (p.pos-pos)*2==(dest-pos))); 
        } else if (name == "horse") {
            return pos.sqrDistance(dest) == 5 and 
                not pieces.some(lambda(p, 
                    p.pos.sqrDistance(pos) == 1 and (p.pos-pos)*(dest-pos)==2));
        } else if (name == "car") {
            auto a = dest-pos;
            return pos.chebyshev(dest) == pos.manhattan(dest) and not pieces.some([&](auto p) {
                auto b = p.pos-pos;
                return b.cross(a)==0 and b.sqrAbs()<a.sqrAbs() and b*a>0;
            });
        } else if (name == "soldier") {
            return pos.chebyshev(dest) == 1;
        } else {  // duck
            auto a = dest-pos;
            return pos.sqrDistance(dest) == 13 and not pieces.some([&](auto p) {
                auto b = p.pos-pos;
                return (a*b==8 and b.sqrAbs()==5) or (a*b==3 and b.sqrAbs()==1);
            });
        }
    }

    bool reachable(Vec2d dest) {  // 能否到达目标地点
        return 0<=dest.x and dest.x<_X and
        0<=dest.y and dest.y<_Y and
        reachable_pos(dest) and 
        not pieces.some(lambda(p, p.pos==dest and p.team==team));
    }
};

namespace Solution {
    int Q;
    void init() {
        std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
        // 添加一个子
        #define add(name,px,py,team) pieces.push_back(Piece{name, {px, py}, Team::team});
        // 添加四个中心对称的子
        #define four(name,dx,dy) add(name,4-dx,4+dy,Red) add(name,4-dx,4-dy,Red) \
            add(name,5+dx,4-dy,Blue) add(name,5+dx,4+dy,Blue)
        // 添加底线上的一个子
        #define bottom(name,dy) four(name,4,dy);
        add("captain",0,4,Red) add("captain",9,4,Blue)
        bottom("car",4)bottom("horse",3)bottom("elephant",2)bottom("guard",1)
        four("duck",2,4)
        four("soldier",1,4)four("soldier",1,2)add("soldier",3,4,Red)add("soldier",6,4,Blue)
        cin >> Q;
    }

    void solve() {
        init();
        // 双方的王
        Piece& kingRed = pieces[0];
        Piece& kingBlue = pieces[1];

        bool round = 0;
        bool gameOver = false;
        from(_, 1, Q) {
            if (gameOver) {  // 游戏结束一定不合法
                cout << "Invalid command\n";
                continue;
            }
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            auto src = Vec2d{x1, y1};  // 起点
            auto dest = Vec2d{x2, y2};  // 终点

            auto selected = std::find_if(pieces.begin(), pieces.end(), 
                lambda(p, p.pos==src and p.team==round));  // 筛选，要求位置一致并且阵营正确
            if (selected == pieces.end()) {  // 没找到
                cout << "Invalid command\n";
                continue;
            }

            bool available = selected->reachable(dest);  // 判断终点位置是否可达
            if (not available) {
                cout << "Invalid command\n"; continue;
            }
            // 主语
            cout << (selected->team==Team::Red? "red ": "blue ") << selected->name << ';';

            // 宾语
            bool isKingKilled = false;  // 王被击杀，判断游戏结束
            auto attackedIter = std::find_if(pieces.begin(), pieces.end(), lambda(p, p.pos==dest));
            selected->pos = dest;
            if (attackedIter == pieces.end()) {
                cout << "NA;";  // 移到空格子
            } else {
                isKingKilled = (attackedIter->name=="captain");  // 游戏结束
                // 输出宾语
                cout << (attackedIter->team==Team::Red? "red ": "blue ") << attackedIter->name << ';';
                pieces.erase(attackedIter);  // 移除被吃的子
            }
            bool isKingInDanger = false;  // 被将军
            isKingInDanger &= !isKingKilled;  // 特判，王已经死了
            isKingInDanger |= pieces.some(lambda(p, p.reachable(kingRed.pos) and p.team==Team::Blue));
            isKingInDanger |= pieces.some(lambda(p, p.reachable(kingBlue.pos) and p.team==Team::Red));
            cout << (isKingInDanger? "yes;": "no;") << (isKingKilled? "yes": "no") << '\n';
            gameOver |= isKingKilled; 
            round ^= 1;  // 当且仅当操作合法，进行轮换
        }
    }
}

int main() {
    Solution::solve();
    return 0;
}