题解：P11649 [COCI 2024/2025 #4] 棋 / Šah

Billhqh9 · 2025-02-01 18:28:42 · 题解

题目链接

洛谷

朴素法

思路：

我们先按题目中说的，用二维数组记录下每个棋子可以攻击到的位置，最后做一个统计。时间复杂度：O(mn+n^2)，可以通过此题。

AC 代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 205;
int n, m, ans;
bool board[maxn][maxn];
int main() {
    cin >> n >> m;
    for(int i = 1; i <= m; ++i) {
        char c;
        int x, y;
        cin >> c >> x >> y;
        board[x][y] = true;
        if(c == 'N') {
            if(x - 2 >= 1 && y - 1 >= 1)
                board[x - 2][y - 1] = true;
            if(x - 2 >= 1 && y + 1 <= n)
                board[x - 2][y + 1] = true;
            if(x - 1 >= 1 && y - 2 >= 1)
                board[x - 1][y - 2] = true;
            if(x - 1 >= 1 && y + 2 <= n)
                board[x - 1][y + 2] = true;
            if(x + 2 >= 1 && y - 1 >= 1)
                board[x + 2][y - 1] = true;
            if(x + 2 >= 1 && y + 1 <= n)
                board[x + 2][y + 1] = true;
            if(x + 1 >= 1 && y - 2 >= 1)
                board[x + 1][y - 2] = true;
            if(x + 1 >= 1 && y + 2 <= n)
                board[x + 1][y + 2] = true;
        }
        if(c == 'R') {
            for(int x1 = x, y1 = y; x1 >= 1; --x1)
                board[x1][y1] = true;
            for(int x1 = x, y1 = y; x1 <= n; ++x1)
                board[x1][y1] = true;
            for(int x1 = x, y1 = y; y1 >= 1; --y1)
                board[x1][y1] = true;
            for(int x1 = x, y1 = y; y1 <= n; ++y1)
                board[x1][y1] = true;
        }
        if(c == 'Q') {
            for(int x1 = x, y1 = y; x1 >= 1; --x1)
                board[x1][y1] = true;
            for(int x1 = x, y1 = y; x1 <= n; ++x1)
                board[x1][y1] = true;
            for(int x1 = x, y1 = y; y1 >= 1; --y1)
                board[x1][y1] = true;
            for(int x1 = x, y1 = y; y1 <= n; ++y1)
                board[x1][y1] = true;
            for(int x1 = x, y1 = y; x1 >= 1 && y1 >= 1; --x1, --y1)
                board[x1][y1] = true;
            for(int x1 = x, y1 = y; x1 >= 1 && y1 <= n; --x1, ++y1)
                board[x1][y1] = true;
            for(int x1 = x, y1 = y; x1 <= n && y1 >= 1; ++x1, --y1)
                board[x1][y1] = true;
            for(int x1 = x, y1 = y; x1 <= n && y1 <= n; ++x1, ++y1)
                board[x1][y1] = true;
        }
    }
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            if(board[i][j] == true)
                ++ans;
    cout << ans << endl;
    return 0;
}

优化法

虽然 AC 了，我们再来想想能不能继续优化。

思路

再使用多个数组记录攻击信息，直接花 O(1) 时间记录行、列、对角线的攻击信息，避免枚举攻击的点。比如用 f1_i 表示第 i 行是否被攻击。这样节省枚举攻击的点的时间，可将时间复杂度的第一项优化一维。时间复杂度：O(m+n^2)。

优化代码

注：在我的代码中 f1_i 表示第 i 行是否被攻击；f2_i 表示第 i 列是否被攻击；f3_i 表示第 i 条从左上往右下的对角线是否被攻击；f4_i 表示第 i 条从右上往左下的对角线是否被攻击。在这里 f1_i 和 f2_i 不用说，但要讲讲在知道坐标的情况下如何算出 f3_i 和 f4_i 中的 i。

对于每条从左上往右下的对角线上的每个坐标为 (x,y) 的点，我们可以发现：x-y 为定值，且每条这样的对角线 x-y 的值都不同。所以计算 i 可以从 x-y 入手，找规律后发现 i 可以表示为 x-y+n。同理，我们可以发现：对于每条从右上往左下的对角线上的每个坐标为 (x,y) 的点，x+y 为定值，且每条这样的对角线 x+y 的值都不同。所以，找规律后发现 i 可以表示为 x+y-1。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 205;
int n, m, ans;
bool board[maxn][maxn], f1[maxn], f2[maxn], f3[maxn * 2], f4[maxn * 2];
int main() {
    cin >> n >> m;
    for(int i = 1; i <= m; ++i) {
        char c;
        int x, y;
        cin >> c >> x >> y;
        board[x][y] = true;
        if(c == 'N') {
            if(x - 2 >= 1 && y - 1 >= 1)
                board[x - 2][y - 1] = true;
            if(x - 2 >= 1 && y + 1 <= n)
                board[x - 2][y + 1] = true;
            if(x - 1 >= 1 && y - 2 >= 1)
                board[x - 1][y - 2] = true;
            if(x - 1 >= 1 && y + 2 <= n)
                board[x - 1][y + 2] = true;
            if(x + 2 >= 1 && y - 1 >= 1)
                board[x + 2][y - 1] = true;
            if(x + 2 >= 1 && y + 1 <= n)
                board[x + 2][y + 1] = true;
            if(x + 1 >= 1 && y - 2 >= 1)
                board[x + 1][y - 2] = true;
            if(x + 1 >= 1 && y + 2 <= n)
                board[x + 1][y + 2] = true;
        }
        if(c == 'R') {
            f1[x] = true;
            f2[y] = true;
        }
        if(c == 'Q') {
            f1[x] = true;
            f2[y] = true;
            f3[x - y + n] = true;
            f4[x + y - 1] = true;
        }
    }
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            if(board[i][j] == true || f1[i] == true || f2[j] == true || f3[i - j + n] == true || f4[i + j - 1] == true)
                ++ans;
    cout << ans << endl;
    return 0;
}

两份代码虽然都能过，但明显第二份代码更快。