Acwing 378.骑士放置(二分图的最大独立集)

简介: 笔记

Acwing 378.骑士放置


题意

给定一个 N×M 的棋盘,有一些格子禁止放棋子。


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


思路

将棋盘划分为两类:坐标和奇数为一类 坐标和偶数为一类,

可以发现 当前格子能到达的格子与其本身奇偶性不同,所以根据坐标和的奇偶性将其抽象成一个二分图,把每个格子和它能到达的格子之间连一条边。


题目要求出最多能放置多少个不能互相攻击的骑士,也即求出最多能放置多少个骑士其两两之间不能到达,即最大独立集的定义:选出最多的点使得其两两之间没有边。


用匈牙利算法求出最大匹配res后,答案即为n * m - k - res。


代码

// Author:zzqwtcc
// Problem: 骑士放置
// Contest: AcWing
// Time:2021-10-07 15:16:37
// URL: https://www.acwing.com/problem/content/380/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
#include<bits/stdc++.h>
#include<unordered_map>
// #define int long long
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define mod 1000000007
#define MOD 998244353
#define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i))
#define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i))
#define debug(x,y) cerr << (x) << " == " << (y) << endl;
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<typename T> inline T lowbit(T x) { return x & -x; }
// template<typename T> T qmi(T a, T b = mod - 2, T p = mod) { T res = 1; b %= (p - 1 == 0 ? p : p - 1); while (b) { if (b & 1) { res = (LL)res * a % p; }b >>= 1; a = (LL)a * a % p; }return res % mod; }
const int N = 110;
int n, m, k;
bool g[N][N];
bool st[N][N];
PII match[N][N];
vector<int>vec[N];
int dx[] = {- 2,-1,1,2,2,1,-1,-2}, dy[] = {1,2,2,1,-1,-2,-2,-1};
bool find(int x,int y){
  for(int i = 0 ;i < 8;++i){
    int a = x + dx[i];
    int b = y + dy[i];
    if(a <= 0 || a > n || b <= 0 || b > m)continue;
    if(st[a][b] || g[a][b])continue;
    st[a][b] = true;
    auto t = match[a][b];
    if(t.first == 0 || find(t.first,t.second)){
      match[a][b] = {x,y};
      return true;
    }
  }
  return false;
}
void solve() {
    cin >> n >> m >> k;
    for( int i = 1; 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 & 1)){
          memset(st,0,sizeof st);
          if(find(i,j))
            res++;
        }
      }
    }
    cout << n * m - k - res << endl;
}
signed main() {
    //int _; cin >> _;
    //while (_--)
        solve();
    return 0;
}


zzqwtc
+关注
目录
打赏
0
0
0
0
1
分享
相关文章
Nacos配置问题之启动项目报错如何解决
Nacos是一个开源的、易于部署的动态服务发现、配置管理和服务管理平台,旨在帮助微服务架构下的应用进行快速配置更新和服务治理;在实际运用中,用户可能会遇到各种报错,本合集将常见的Nacos报错问题进行归纳和解答,以便使用者能够快速定位和解决这些问题。
5328 77
kde
|
10天前
|
Docker镜像加速指南:手把手教你配置国内镜像源
配置国内镜像源可大幅提升 Docker 拉取速度,解决访问 Docker Hub 缓慢问题。本文详解 Linux、Docker Desktop 配置方法,并提供测速对比与常见问题解答,附最新可用镜像源列表,助力高效开发部署。
kde
6709 15
|
7天前
typora免费版,激活方法,Typora使用教程
Typora是一款简洁高效的Markdown编辑器,支持即时渲染。本教程涵盖安装方法、文件操作、视图控制、格式排版、字体样式及Markdown语法,助你快速上手使用Typora进行高效写作。
1733 1
Dify MCP 保姆级教程来了!
大语言模型,例如 DeepSeek,如果不能联网、不能操作外部工具,只能是聊天机器人。除了聊天没什么可做的。
1691 26
国内如何安装和使用 Claude Code镜像教程 - Windows 用户篇
国内如何安装和使用 Claude Code镜像教程 - Windows 用户篇
1015 5
【保姆级图文详解】大模型、Spring AI编程调用大模型
【保姆级图文详解】大模型、Spring AI编程调用大模型
686 9
【保姆级图文详解】大模型、Spring AI编程调用大模型
2025年最新版最细致Maven安装与配置指南(任何版本都可以依据本文章配置)
本文详细介绍了Maven的项目管理工具特性、安装步骤和配置方法。主要内容包括: Maven概述:解释Maven作为基于POM的构建工具,具备依赖管理、构建生命周期和仓库管理等功能。 安装步骤: 从官网下载最新版本 解压到指定目录 创建本地仓库文件夹 关键配置: 修改settings.xml文件 配置阿里云和清华大学镜像仓库以加速依赖下载 设置本地仓库路径 附加说明:包含详细的配置示例和截图指导,适用于各种操作系统环境。 本文提供了完整的Maven安装和配置
2025年最新版最细致Maven安装与配置指南(任何版本都可以依据本文章配置)
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问