题解：骑士放置问题

一、题目背景

给定一个 (N×M) 的棋盘，部分格子禁止放棋子，要求在棋盘上放置国际象棋中的“骑士”（类似中国象棋的“马”，按“日”字攻击且无“别马腿”规则），求最多能放置多少个且这些骑士不能互相攻击。

二、解题思路

本题可通过构建二分图并利用匈牙利算法求最大匹配来解决。将棋盘上的格子看作图的节点，能互相攻击的两个格子对应的节点之间连边。由于按“日”字攻击的特性，可将棋盘上的格子根据横纵坐标之和的奇偶性分成两部分，使同一部分内的格子不能互相攻击，从而构成二分图。然后使用匈牙利算法求这个二分图的最大匹配，用棋盘总格子数减去禁止放置的格子数，再减去最大匹配数，就是最多能放置的互不攻击的骑士数量。

具体步骤如下：
1. 定义相关数组和变量，包括存储棋盘状态的二维数组 g[N][N]（true 表示该格子禁止放置）、记录匹配情况的二维数组 match[N][N]（存储匹配的节点对）、标记节点是否已访问的二维数组 st[N][N]、表示“骑士”按“日”字移动的偏移量数组 dx[8] 和 dy[8]。
2. 编写匈牙利算法的核心函数 find，用于寻找增广路径：
- 遍历“骑士”按“日”字可移动到的八个方向。
- 检查移动后的坐标是否在棋盘内、不是禁止放置的格子且未被访问过。
- 标记移动后的节点为已访问，若该节点未匹配，或者能通过递归找到增广路径，则更新匹配关系并返回 true。
- 若所有方向都无法找到增广路径，则返回 false。
3. 在 main 函数中：
- 读取棋盘的行数 n、列数 m 和禁止放置的格子数量 k。
- 读取每个禁止放置的格子坐标，更新棋盘状态数组 g。
- 初始化结果变量 res 为 (0)，遍历所有横纵坐标之和为偶数且不是禁止放置的格子（选择其中一部分进行匹配尝试即可，这里选偶数）：
- 每次匹配尝试前，将访问标记数组 st 清零。
- 调用 find 函数进行匹配尝试，若匹配成功则结果 res 加 (1)。
- 输出最多能放置的互不攻击的骑士数量，计算公式为 n * m - k - res（n * m 是棋盘总格子数，k 是禁止放置的格子数，res 是最大匹配数）。

三、代码逐段分析

（一）头文件、宏定义和全局变量

#include <cstring>
#include <iostream>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 110;

int n, m, k;
PII match[N][N];
bool g[N][N], st[N][N];
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};

1. 头文件：
   • #include <cstring>：用于字符串操作和内存初始化函数，如 memset。
   • #include <iostream>：提供C++风格的输入输出流，如 cin 和 cout。
   • #include <algorithm>：包含一些常用的算法函数。
2. 宏定义：#define x first 和 #define y second 用于简化对 pair 类型元素的访问。
3. 类型定义：typedef pair<int, int> PII; 定义 PII 为 pair<int, int> 类型，方便表示坐标。
4. 常量定义：const int N = 110; 定义棋盘大小的最大值。
5. 变量定义：
   • int n, m, k;：分别表示棋盘的行数、列数和禁止放置的格子数量。
   • PII match[N][N];：二维数组，存储每个格子的匹配情况，每个元素是一个 PII 类型，记录匹配的另一个格子的坐标。
   • bool g[N][N], st[N][N];：g[N][N] 表示棋盘状态，true 表示该格子禁止放置；st[N][N] 用于标记在一次匹配尝试中，节点是否已被访问。
   • int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2}; 和 int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};：表示“骑士”按“日”字移动的八个方向的偏移量数组。

（二）匈牙利算法函数 find

bool find(int x, int y)
{
    for (int i = 0; i < 8; i ++ )
    {
        int a = x + dx[i], b = y + dy[i];
        if (a < 1 || a > n || b < 1 || b > m) continue;
        if (g[a][b]) continue;
        if (st[a][b]) continue;

        st[a][b] = true;

        PII t = match[a][b];
        if (t.x == 0 || find(t.x, t.y))
        {
            match[a][b] = {x, y};
            return true;
        }
    }

    return false;
}

1. 遍历“骑士”按“日”字可移动到的八个方向：
   • 根据偏移量数组计算移动后的坐标 (a, b)。
   • 检查移动后的坐标是否在棋盘内（a 在 1 到 n 之间且 b 在 1 到 m 之间）、不是禁止放置的格子（!g[a][b]）且未被访问过（!st[a][b]）。
2. 若移动后的坐标满足条件：
   • 标记该坐标对应的节点为已访问（st[a][b] = true;）。
   • 获取该节点当前的匹配情况 t。
   • 若该节点未匹配（t.x == 0），或者能通过递归调用 find 函数为该节点的当前匹配对象找到新的匹配（find(t.x, t.y)），则更新该节点的匹配为当前节点 (x, y)，并返回 true。
3. 若所有方向都无法找到增广路径，则返回 false。

（三）main 函数

int main()
{
    cin >> n >> m >> k;

    for (int i = 0; i < k; i ++ )
    {
        int x, y;
        cin >> x >> y;
        g[x][y] = true;
    }

    int res = 0;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        {
            if (g[i][j] || (i + j) % 2) continue;
            memset(st, 0, sizeof st);
            if (find(i, j)) res ++ ;
        }

    cout << n * m - k - res << endl;

    return 0;
}

1. 读取棋盘的行数 n、列数 m 和禁止放置的格子数量 k。
2. 读取每个禁止放置的格子坐标 (x, y)，并将棋盘状态数组 g[x][y] 设置为 true。
3. 初始化结果变量 res = 0，遍历所有横纵坐标之和为偶数且不是禁止放置的格子：
   • 每次匹配尝试前，将访问标记数组 st 清零。
   • 调用 find 函数进行匹配尝试，若匹配成功（find(i, j) 返回 true），则结果 res 加 (1)。
4. 输出最多能放置的互不攻击的骑士数量，计算公式为 n * m - k - res。
5. 程序结束。

四、时间复杂度和空间复杂度分析

（一）时间复杂度

1. 读入数据：读取禁止放置的格子坐标，时间复杂度为 (O(k))，其中 (k) 是禁止放置的格子数量。
2. 匈牙利算法：对于每个可放置且横纵坐标之和为偶数的格子，最多进行 (O(8)) 次匹配尝试（因为“骑士”按“日”字最多有 8 个可移动方向），而这样的格子最多有 (O(nm)) 个，所以匈牙利算法的时间复杂度为 (O(nm))。
   总体时间复杂度为 (O(k + nm))。

（二）空间复杂度

1. 数组空间：棋盘状态数组 g[N][N]、匹配数组 match[N][N]、访问标记数组 st[N][N] 等，空间复杂度均为 (O(nm))。
   总体空间复杂度为 (O(nm))。

希望这份题解能帮助你理解这道题的解题思路和代码实现。如果有任何疑问，欢迎随时提问。