AcWing 372. 棋盘覆盖
原题链接
中等
作者:
zqc
,
2021-05-12 10:03:41
,
所有人可见
,
阅读 339
#include <bits/stdc++.h>
using namespace std;
using PII = pair<int, int>;
const int N = 110;
PII match[N][N];
bool st[N][N], g[N][N];
int n, t;
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 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) continue;
if (st[a][b] || g[a][b]) continue;
st[a][b] = true;
PII tt = match[a][b];
int tx = tt.first, ty = tt.second;
if ((tx == 0 && ty == 0) || find(tx, ty))
{
match[a][b] = {x, y};
return true;
}
}
return false;
}
int main(void)
{
scanf("%d%d", &n, &t);
for (int i = 0; i < t; i ++)
{
int a, b;
cin >> a >> b;
g[a][b] = true;
}
int res = 0;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
if ((i + j) % 2 && !g[i][j])
{ memset(st, 0, sizeof st);
if (find(i ,j))
res ++;
}
printf("%d", res);
return 0;
}
兄弟有时间填个邀请码hhhhhhhhh(可以得AC币,邀请码在学生认证那填) 我的邀请码是:GUDFH