正经题解｜危在旦夕的国王

题目解析

使用二维数组 grid[N][N] 来表示棋盘上的棋子，把棋盘上所有除了国王以外的棋子标记为 $1$。

使用二维数组 state[N][N] 来表示棋盘上各个位置上是否可以被攻击到，可以攻击到的位置标记为 $1$。

实现以下功能：

1. int f(char ch)： 将棋子的坐标转化为容易处理的整数。

2. int check(int x, int y)：检测 $(x, y)$ 是否越界。

3. move(int x, int y, int dx, int dy)：表示以坐标 $(x, y)$ 为起点，坐标 $\Delta$ 为 $[dx, dy]$ 移动并将 $state[x + dx \times c][y + dy \times c], (c \in{\mathbb{Z}})$ 标记为 $1$。

4. queen(x, y)：将位置在 $(x, y)$ 上的皇后可以走到的位置标记为 $1$。

5. pawn(x, y)：将位置在 $(x, y)$ 上的兵可以走到的位置标记为 $1$。

6. rook(x, y)：将位置在 $(x, y)$ 上的车可以走到的位置标记为 $1$。

7. bishop(x, y)：将位置在 $(x, y)$ 上的主教可以走到的位置标记为 $1$。

8. knight(x, y)：将位置在 $(x, y)$ 上的骑士可以走到的位置标记为 $1$。

若国王的位置为$(x, y)$，且被将军则 $state[x][y] = 1$，否则 $state[x][y] = 0$。

检测国王周围的最多可以走到的 $8$ 个位置 $(x', y')$ 若存在 $state[x'][y'] = 0$ 则国王可以可以走到一个不会被将军的新格子中。

按照题意检测上述两个条件即可得到棋盘的状态。

AC代码

#include <bits/stdc++.h>
using namespace std;

constexpr int N = 8;

constexpr int dirs[][2] {0, 1, 1, 0, 0, -1, -1, 0};

int grid[N][N], state[N][N];

int f(char ch) {
    return isalpha(ch) ? ch - 'a' : N - (ch - '0');
}

int check(int x, int y) {
    return x >= 0 and x < N and y >= 0 and y < N;
}

void move(int x, int y, int dx, int dy) {
    x += dx, y += dy;
    while (check(x, y)) {
        state[x][y] = 1;
        if (grid[x][y] == 1) break;
        x += dx;
        y += dy;
    }
}

void queen(int x, int y) {
    for (int dx = -1; dx <= 1; ++dx)
        for (int dy = -1; dy <= 1; ++dy)
            if (dx != 0 or dy != 0)
                move(x, y, dx, dy);
}

void pawn(int x, int y) {
    if (x - 1 >= 0 and y - 1 >= 0)
        state[x - 1][y - 1] = 1;
    if (x - 1 >= 0 and y + 1 < N)
        state[x - 1][y + 1] = 1;
}

void rook(int x, int y) {
    for (auto &[dx, dy] : dirs)
        move(x, y, dx, dy);
}

void bishop(int x, int y) {
    for (int dx = -1; dx <= 1; ++dx)
        for (int dy = -1; dy <= 1; ++dy)
            if (dx != 0 and dy != 0)
                move(x, y, dx, dy);
}

void knight(int x, int y) {
    for (int i = 0; i < 2; ++i)
        for (int dx = -1; dx <= 1; ++dx)
            for (int dy = -1; dy <= 1; ++dy) {
                if (dx == 0 or dy == 0) continue;
                int nx = x + dx, ny = y + dy;
                if (i == 0) nx += dx;
                else        ny += dy;
                if (check(nx, ny))
                    state[nx][ny] = 1;
            }
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; cin >> _;
    while (_--) {
        memset(grid, 0, sizeof grid);
        memset(state, 0, sizeof state);
        int n; cin >> n;
        vector<string> pices(n);
        int x, y;
        for (auto &pice : pices) {
            cin >> pice;
            if (pice[0] != 'K')
                grid[f(pice[2])][f(pice[1])] = 1;
        }
        for (auto &pice : pices) {
            int xx = f(pice[2]), yy = f(pice[1]);
            switch (pice[0]) {
                case 'K': x = xx, y = yy; break;
                case 'Q': queen(xx, yy); break;
                case 'P': pawn(xx, yy); break;
                case 'B': bishop(xx, yy); break;
                case 'N': knight(xx, yy); break;
                case 'R': rook(xx, yy); break;
            }
        }
        bool adj = false;
        for (int dx = -1; dx <= 1; ++dx)
            for (int dy = -1; dy <= 1; ++dy) {
                if (dx == 0 and dy == 0) continue;
                int nx = x + dx, ny = y + dy;
                if (check(nx, ny) and state[nx][ny] == 0)
                    adj = true;
            }
        if (state[x][y] == 0 and adj)
            cout << "SAFE\n";
        else if (state[x][y] == 1 and adj)
            cout << "CHECK\n";
        else if (state[x][y] == 1 and adj == false)
            cout << "CHECKMATE\n";
        else if (state[x][y] == 0 and adj == false)
            cout << "STALEMATE\n";
    }
    return 0;
}

复杂度分析

令棋盘的长度为 $M$。
则将每个棋子可以攻击到的位置标记的时间复杂度为 $O(M^2)$。
总的时间复杂度为 $O(NM^2)$。