题目描述
给定一个 N×M 的棋盘,有一些格子禁止放棋子。
问棋盘上最多能放多少个不能互相攻击的骑士(国际象棋的“骑士”,类似于中国象棋的“马”,按照“日”字攻击,但没有中国象棋“别马腿”的规则)。
输入格式
第一行包含三个整数 N,M,T,其中 T 表示禁止放置的格子的数量。
接下来 T 行每行包含两个整数 x 和 y,表示位于第 x 行第 y 列的格子禁止放置,行列数从 1 开始。
输出格式
输出一个整数表示结果。
数据范围
1≤N,M≤100
样例
输入样例:
2 3 0
输出样例:
4
算法1
C++ 代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5;
int n,m,t;
int head[N],idx = 0,match[N];
bool vis[N];
struct edge{
int to;
int next;
}e[N];
void add(int u,int v)
{
e[++idx].to = v;
e[idx].next = head[u];
head[u] = idx;
}
int find(int u)
{
for(int i = head[u]; i; i = e[i].next)
{
int v = e[i].to;
if(!vis[v])
{
vis[v] = true;
if(!match[v] || find(match[v]))
{
match[v] = u;
return true;
}
}
}
return false;
}
int num(int x,int y)
{
return (x - 1) * m + y;
}
int tot;
int res;
int flag[N];
int main()
{
scanf("%d%d%d",&n,&m,&t);
memset(flag, false, sizeof(flag));
for(int i = 1;i <= t;i ++){
int a,b;
scanf("%d%d",&a,&b);
if(flag[num(a,b)]) continue;
flag[num(a,b)] = true;
tot ++;
}
int dx[8]={-1,-1,-2,-2,1,1,2,2};
int dy[8]={-2,2,-1,1,-2,2,-1,1};
for(int i = 1;i <= n;i ++)
{
for(int j = 1;j <= m;j ++)
{
if(!flag[num(i,j)])
{
int u = num(i,j);
for(int k = 0;k < 8;k ++)
{
int x = i + dx[k];
int y = j + dy[k];
if(x >= 1 && x <= n && y >= 1 && y <= m && !flag[num(x,y)])
{
add(u,num(x,y));
}
}
}
}
}
for(int i = 1;i <= n;i ++){
for(int j = 1;j <= m;j ++){
memset(vis,false, sizeof(vis));
if(find(num(i,j)) && !flag[(num(i,j))]) res++;
}
}
printf("%d", n * m - res / 2 - tot);
return 0;
}