NC51277. 骑士放置
描述
给定一个 N*M 的棋盘，有一些格子禁止放棋子。
问棋盘上最多能放多少个不能互相攻击的骑士（国际象棋的“骑士”，类似于中国象棋的“马”，按照“日”字攻击，但没有中国象棋“别马腿”的规则）。
输入描述
第一行包含三个整数N,M,T，其中T表示禁止放置的格子的数量。
接下来T行每行包含两个整数x和y，表示位于第x行第y列的格子禁止放置，行列数从1开始。
输出描述
输出一个整数表示结果。
示例1
输入:
2 3 0
输出:
4
C++14(g++5.4) 解法, 执行用时: 303ms, 内存消耗: 624K, 提交时间: 2020-08-14 15:50:19
#include<bits/stdc++.h>
using namespace std;
const int N = 105;
int n, m, t, ans, fx[N][N], fy[N][N];
bool a[N][N], v[N][N];
const int dx[8] = { -2, -2, -1, -1, 1, 1, 2, 2 };
const int dy[8] = { -1, 1, -2, 2, -2, 2, -1, 1 };
bool dfs(int x, int y) {
for (int i = 0; i < 8; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 1 || ny < 1 || nx > n || ny > m || a[nx][ny]) continue;
if (v[nx][ny]) continue;
v[nx][ny] = 1;
if (fx[nx][ny] == 0 || dfs(fx[nx][ny], fy[nx][ny])) {
fx[nx][ny] = x, fy[nx][ny] = y;
return true;
}
}
return false;
}
int main() {
//freopen("in.txt", "r", stdin);
cin >> n >> m >> t;
for (int i = 0; i < t; ++i) {
int x, y; cin >> x >> y;
a[x][y] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (i + j & 1) continue;
if (a[i][j]) continue;
memset(v, 0, sizeof(v));
if (dfs(i, j)) ans++;
}
}
cout << n * m - t - ans << endl;
}
C++ 解法, 执行用时: 293ms, 内存消耗: 756K, 提交时间: 2022-04-16 09:46:07
#include<bits/stdc++.h>
using namespace std;
const int N = 105;
int n, m, t, ans, fx[N][N], fy[N][N],x,y;
bool a[N][N], v[N][N];
const int dx[8] = { -2, -2, -1, -1, 1, 1, 2, 2 };
const int dy[8] = { -1, 1, -2, 2, -2, 2, -1, 1 };
bool dfs(int x, int y) {
for (int i = 0; i < 8; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 1 || ny < 1 || nx > n || ny > m || a[nx][ny]) continue;
if (v[nx][ny]) continue;
v[nx][ny] = 1;
if (fx[nx][ny] == 0 || dfs(fx[nx][ny], fy[nx][ny])) {
fx[nx][ny] = x, fy[nx][ny] = y;
return true;
}
}
return false;
}
int main() {
cin >> n >> m >> t;
for (int i = 0; i < t;i++)cin >> x >> y,a[x][y] = 1;
for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++) {
if (i + j & 1) continue;
if (a[i][j]) continue;
memset(v, 0, sizeof(v));
if (dfs(i, j)) ans++;
}
cout<<n*m-t-ans;
}