象棋马的走法规则及吃子判定 - C++ 代码实现 - 常规

象棋马的走法规则及吃子判定 - C++ 代码实现

题目描述

投完篮后小X浑身酸爽，心情愉快地备课去了，第一次上课首先要教小朋友们各种棋子的走法，并且要设计练习帮助小朋友们巩固记忆。小X发现马的跳法将是第一节课的难点，首先马的走法很不规则，它是先沿着直线走一格，然后再沿着斜线走一格，也就是俗称的‘马走日’，但中国象棋与国际象棋有所不同，首先中国象棋是从一个交叉点上移动到另一个交叉点上，而国际象棋棋子则在方格中移动；其次，中国象棋的马还有‘蹩马脚’的规则，即如果在马前行的道路上有一个棋子（该棋子可以是任意一方的）则称马被蹩住脚了，它就跳不到相应的位置上，这个‘蹩’字读'别'，意思为'绊'。

下图为马的走法规则：

‘马走日’的行棋有条规定：马先沿亘线走一格，然后再沿斜线走一格。马每次跳一个‘日’字，就是从‘日’字的一个角走到其对角，不管这个‘日’字是立着还是横着，只要没有被蹩住脚，它都可以跳过去。当马在棋盘中部的时候，如果没有障碍，最多能够看管住8个点，所以人们夸它是‘八面威风’。如果跳到边线上，它的威力就小多了，我们看到红马在边线上，最多可以看管住4个点，减少了一半的管辖范围。如果跳到角上，则威力再减半！

但是马有一个很大的弱点——害怕被‘蹩马脚’，也叫‘绊马脚’。一旦马脚被蹩，就寸步难行。怎样是‘蹩马脚’呢？如果紧邻马行进方向的交叉点上有一个棋子（可以是任何一方棋子），马就不能跳过去，这就是‘蹩马脚’，如下图中所示。如果在交叉点A处有一枚棋子，则图中的马就跳不到1和2两个交叉点上了；同理如果在交叉点B处有一枚棋子，则图中的马就跳不到3和4两个交叉点上了，如果在交叉点C处有一枚棋子，则图中的马就跳不到5和6两个交叉点上了，如果在交叉点D处有一枚棋子，则图中的马就跳不到7和8两个交叉点上了。

现在小X给你一个棋盘上的局面，此局面最多会有两个马，并且如果有两个马则它们一定是同一方的，另外还有许多别的棋子分布在棋盘上，这些棋子可能是己方的，也可能是对方的。小X要你指出有多少个对方的棋子会被马吃到，只要是在马一步能跳到的位置上有一个对方的棋子，则马就能吃到这个棋子。在象棋规则中任何时候任何棋子都不能吃己方的棋子！

输入：

输入数据第一行为一个正整数n, 表示1或2，表示棋盘上有n个马，这n个马属于同一方。接下来n行每行包含两个整数表示马的位置，如果有两个马，则它们的位置保证不相同。

接下来的第n+2行为一个整数m, 表示棋盘上有m个棋子，最后m行每行有3个整数，表示一个棋子的信息，前两个数为棋子的位置，第三个数表示该棋子与马的关系。0表示它与马是同一方的，可以蹩马脚，但不可以被马吃；1表示它与马不是同一方的，既可以蹩马脚，又可以被马吃。棋盘上的位置是这样表示的，我们把棋盘上的每条竖线从左往右编号为1~9，把棋盘上的每条横线从下往上编号为1~10。

输出：

输出数据仅有一行包含一个整数，表示马能够吃到的对方棋子的数量。如果一个棋子同时被两个马吃到，这个棋子只能被统计一次！

样例输入：

样例输出：

提示：

这匹马只能吃到(6,5)位置上的棋子。(3,8)和(5,8)被(4,7)蹩马脚了，(6,7)则是自己一方的棋子。

70%的数据棋盘上只有一个马，且其中30%的数据不存在“蹩马脚”的情况。

100%的数据棋盘上最多只有两个马，同一位置保证只有一个棋子，并且位置不会超出棋盘的范围。

代码实现 (C++):

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<int>> board(10, vector<int>(9, 0));
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        board[x][y] = 1; // 马的位置
    }
    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        int x, y, relation;
        cin >> x >> y >> relation;
        if (relation == 1) {
            board[x][y] = -1; // 对方棋子的位置
        }
    }
    int count = 0;
    int dx[8] = {1, 1, 2, 2, -1, -1, -2, -2};
    int dy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y; // 再次输入马的位置，可能需要优化
        for (int j = 0; j < 8; j++) {
            int nx = x + dx[j];
            int ny = y + dy[j];
            if (nx >= 1 && nx <= 9 && ny >= 1 && ny <= 8 && board[nx][ny] == -1) {
                count++;
            }
        }
    }
    cout << count << endl;
    return 0;
}

时间复杂度分析：

遍历马的位置的时间复杂度是O(n)，遍历棋子信息的时间复杂度是O(m)，遍历马的位置判断是否有对方棋子的时间复杂度是O(n)，总的时间复杂度是O(n+m)。

优化建议:

可以将马的位置信息在读取时直接存储到 dx 和 dy 数组中，避免重复读取。
可以使用 set 或 unordered_set 来记录已经被吃掉的棋子，避免重复计数。

希望本文能够帮助您更好地理解象棋马的走法规则，并能够运用 C++ 代码实现相应的逻辑判断。如果您有任何问题或建议，欢迎随时提出。