算法竞赛备考冲刺必刷题（C++） | AcWing 378 骑士放置

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

AcWing：378. 骑士放置 - AcWing题库

【题目描述】

给定一个 $N\times M$ 的棋盘，有一些格子禁止放棋子。

问棋盘上最多能放多少个不能互相攻击的骑士（国际象棋的“骑士”，类似于中国象棋的“马”，按照“日”字攻击，但没有中国象棋“别马腿”的规则）。

【输入】

第一行包含三个整数 $N,M,T$，其中 $T$ 表示禁止放置的格子的数量。

接下来 $T$ 行每行包含两个整数 $x$ 和 $y$，表示位于第 $x$ 行第 $y$ 列的格子禁止放置，行列数从 $1$ 开始。

【输出】

输出一个整数表示结果。

【输入样例】

2 3 0

【输出样例】

4

【算法标签】

《AcWing 378 骑士放置》 #图论# #二分图最大独立集# #匈牙利算法#

【代码详解】

#include <bits/stdc++.h>  // 包含标准库头文件（万能头文件）
using namespace std;      // 使用标准命名空间

typedef pair<int, int> PII;  // 定义坐标对类型
const int N = 105;           // 定义常量：棋盘最大尺寸

int n, m, k;                  // 定义变量：棋盘行数n，列数m，禁放格子数k
PII match[N][N];              // 定义数组：存储每个格子的匹配对象
bool g[N][N], st[N][N];       // 定义数组：g[i][j]表示是否为禁放格子，st[i][j]表示是否已访问

// 马走日的8个方向
int dx[8] = {-2, -2, -1, 1, 2, 2, 1, -1};
int dy[8] = {-1, 1, 2, 2, 1, -1, -2, -2};

/**
 * 匈牙利算法寻找增广路径
 * @param x 当前格子的行坐标
 * @param y 当前格子的列坐标
 * @return 是否找到增广路径
 */
bool find(int x, int y) 
{
    // 遍历8个可能的方向
    for (int i = 0; i < 8; i++) 
    {
        int nx = x + dx[i], ny = y + dy[i];  // 计算新坐标
        
        // 检查新坐标是否合法
        if (nx < 1 || nx > n || ny < 1 || ny > m || g[nx][ny] || st[nx][ny]) 
            continue;
        
        st[nx][ny] = true;  // 标记为已访问
        PII t = match[nx][ny];  // 获取当前匹配
        
        // 如果新格子未匹配或能找到新的匹配
        if (t.first == -1 || find(t.first, t.second) == true) 
        {
            match[nx][ny] = {x, y};  // 更新匹配关系
            return true;
        }
    }
    return false;
}

int main()
{
    cin >> n >> m >> k;  // 输入棋盘尺寸和禁放格子数
    memset(match, -1, sizeof(match));  // 初始化匹配数组
    
    // 标记禁放格子
    for (int i = 1; i <= k; i++) 
    {
        int x, y;
        cin >> x >> y;
        g[x][y] = true;
    }
    
    int ans = 0;  // 定义变量：存储最大匹配数
    
    // 遍历棋盘上的每个格子（只处理非禁放且行列和为偶数的格子）
    for (int i = 1; i <= n; i++) 
    {
        for (int j = 1; j <= m; j++) 
        {
            if (g[i][j] == true || (i + j) % 2 == 1) 
                continue;
            
            memset(st, false, sizeof(st));  // 重置访问标记
            if (find(i, j) == true) 
                ans++;  // 找到匹配则计数
        }
    }
    
    // 输出结果：总格子数 - 禁放数 - 最大匹配数
    cout << n * m - k - ans << endl;
    
    return 0;  // 程序正常结束
}

【运行结果】

2 3 0
4