分析
把方格看成点,若两点间能互相攻击,则连一条无向边,问题等价于最多能选多少点,使得任意两点间没有边,即最大独立集
最大独立集在一般图上是 NP-hard 问题,考察图是否为二分图:对于任意点 $(x, y)$,它能攻击到的八个方向的坐标和为 $x + y + (奇 + 偶)$,与 $x + y$ 的奇偶性不同,因此所有边的端点都能按奇偶性分成两组,因此是二分图。最终答案 = 总点数 - 禁止放置的方格 - 最大匹配数
#include <cstring>
#include <iostream>
using namespace std;
const int N = 110;
int n, m, k;
pair<int, int> match[N][N];
bool g[N][N], st[N][N];
int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
bool find(int x, int y) {
for (int i = 7; ~i; i --) {
int a = x + dx[i], b = y + dy[i];
if (a < 1 || a > n || b < 1 || b > m) continue;
if (!g[a][b] && !st[a][b]) {
st[a][b] = 1;
auto& [tx, ty] = match[a][b];
if (!tx || find(tx, ty))
return tx = x, ty = y;
}
}
return 0;
}
int main() {
cin >> n >> m >> k;
for (int i = 0, x, y; i < k; i ++)
cin >> x >> y, g[x][y] = 1;
int mch = 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)) mch ++;
}
cout << n * m - k - mch << endl;
return 0;
}
抽象模型,赞
e……应该是NP-hard吧,NP-hardness是一种性质
好的,谢谢