AcWing 378. 骑士放置
原题链接
简单
作者:
每天少秃一点
,
2021-08-20 18:16:41
,
所有人可见
,
阅读 256
C++ 代码
//类似372棋盘覆盖 只不过372是求最大匹配数 这题是求最大独立集
#include <iostream>
#include <cstring>
using namespace std;
const int N = 110;
typedef pair<int, int> PII;
int g[N][N];
bool st[N][N];
PII ret[N][N];
int dx[8] = {-2, -2, -1, 1, 2, 2, 1, -1};
int dy[8] = {-1, 1, 2, 2, 1, -1, -2, -2};
int n, m, t;
bool find(PII t) {
for (int i = 0;i < 8;i++) {
int a = t.first + dx[i], b = t.second + dy[i];
if (a <= 0 || a > n || b <= 0 || b > m || g[a][b] || st[a][b]) continue;
st[a][b] = true;
if (ret[a][b].first == 0 || find(ret[a][b])) {
ret[a][b] = t;
return true;
}
}
return false;
}
int main()
{
cin >> n >> m >> t;
int x, y;
for (int i = 0;i < t;i++) {
cin >> x >> y;
g[x][y] = 1;
}
int res = 0;
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= m; j ++ ) {
if ((i + j) % 2 == 0 || g[i][j]) continue;
memset(st, false, sizeof st);
if (find({i, j})) res++;
}
}
cout << n * m - t - res << endl;
return 0;
}