AcWing 372. 棋盘覆盖
原题链接
中等
作者:
小念
,
2022-02-15 23:52:56
,
所有人可见
,
阅读 158
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 110;
int g[N][N], n, t;//g记录被占用的格子
bool st[N][N];//记录是否尝试匹配过
int match[N][N][2];//记录是否匹配成功
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
bool find(int x, int y)
{
for(int i = 0; i < 4; i ++)
{
int a = x + dx[i], b = y + dy[i];
if(a >= 1 && a <= n && b >= 1 && b <= n && !st[a][b] && !g[a][b])
{
st[a][b] = true;
if(match[a][b][0] == 0 || find(match[a][b][0], match[a][b][1]))
{
match[a][b][0] = x, match[a][b][1] = y;
return true;
}
}
}
return false;
}
int main()
{
cin >> n >> t;
while(t --)
{
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 <= n; j ++)
{
memset(st, 0, sizeof st);
if((i + j) % 2 && !g[i][j] && find(i, j)) ans ++;//i+j 为奇为偶都一样,随便选取一个
}
cout << ans << endl;
return 0;
}