其实做这种棋盘上的题目，其实可以考虑，把棋盘按黑白间隔分成两部分
这里，对于 (i,j) 如果将 (i+j)%2 == 1 定义为奇数位 ， 反之就是偶数位
比较有趣的是，奇数位的骑士能走一步能到达的位置一定是偶数位，同样，偶数位能到达的位置一定是奇数位
所以，就可以把奇数位，偶数位放两侧，将走一步能到达的点连起来，形成一个二分图
题目要求的答案就是 总点数-障碍点-二分图的最大匹配
#include <bits/stdc++.h>
#define pos(x, y) (x-1)*n+y
const int maxn = 205;
using namespace std;
typedef long long ll;
int xiang[8][2] = {{1,2},{1,-2},{-1,2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1}};
vector <int> maps[maxn*maxn];
int bar[maxn*maxn], mark[maxn*maxn];
int pipei[maxn*maxn];
int n, m;
bool dfs(int u){
for(int i=0, len=maps[u].size(); i<len; i++){
int v = maps[u][i];
if(!mark[v]){
mark[v] = true;
if(!pipei[v] || dfs(pipei[v])){
pipei[v] = u;
return true;
}
}
}
return false;
}
int main()
{
scanf("%d%d", &n, &m);
for(int i=1; i<=m; i++){
int a, b;
scanf("%d%d", &a, &b);
bar[pos(a, b)] = true;
}
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
int u = pos(i, j);
if((i+j)%2 && !bar[u]){ //该点是奇数点，而且没有障碍
for(int d=0; d<8; d++){
int tx = i + xiang[d][0];
int ty = j + xiang[d][1];
int v = pos(tx, ty);
if(tx < 1 || ty < 1 || tx > n || ty > n || bar[v])
continue;//越界或者有障碍
maps[u].push_back(v);
maps[v].push_back(u);
}
}
}
}
int ans = 0;
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
int x = pos(i, j);
if((i+j)%2 && !bar[x]){ //奇数位匹配偶数位
memset(mark, false, sizeof(mark));
if(dfs(x))
ans++;
}
}
}
printf("%d
", n*n - m - ans); //总点数 - 障碍数 - 最大匹配
return 0;
}
同样最大流也可以计算出二分图的最大匹配
#include <bits/stdc++.h>
#define pos(x, y) (x-1)*n + y
const int maxn = 205;
const int inf = 0x3f3f3f3f;
using namespace std;
int xiang[8][2] = {{1,2},{1,-2},{-1,2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1}};
struct note{
int u, v, w;
int next;
} e[maxn*maxn*20];
int head[maxn*maxn], cnt;
int n, m, s, t;
bool bar[maxn][maxn];
void add(int u, int v, int w){
e[cnt] = (note){u, v, w, head[u]};
head[u] = cnt++;
e[cnt] = (note){v, u, 0, head[v]};
head[v] = cnt++;
}
int level[maxn*maxn];
bool bfs(){
memset(level, -1, sizeof(level));
level[s] = 1;
queue<int> q;
q.push(s);
while(!q.empty()){
int u = q.front();
q.pop();
for(int i=head[u]; i; i=e[i].next){
int v = e[i].v;
if(e[i].w > 0 && level[v] == -1){
level[v] = level[u] + 1;
q.push(v);
}
}
}
return level[t] != -1;
}
int dfs(int u, int delta){
if(u == t)
return delta;
int flow = 0, tmp;
for(int i=head[u]; i; i=e[i].next){
int v = e[i].v;
if(e[i].w > 0 && level[u] + 1 == level[v]){
tmp = dfs(v, min(delta-flow, e[i].w));
e[i].w -= tmp;
e[i^1].w += tmp;
flow += tmp;
if(flow == delta)
return flow;
}
}
if(flow == 0)
level[u] = -1;
return flow;
}
int Dinic(){
int maxflow = 0, tmp;
while(bfs()){
while((tmp=dfs(s, inf)))
maxflow += tmp;
}
return maxflow;
}
int main()
{
scanf("%d%d", &n, &m);
s = 0, t = n*n+1;
cnt = 2;
for(int i=0; i<m; i++){
int a, b;
scanf("%d%d", &a, &b);
bar[a][b] = true;
}
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
if((i+j)%2 && !bar[i][j]){
int u = pos(i, j);
add(s, u, 1); //源点 --> 奇数位
for(int d=0; d<8; d++){
int tx = i + xiang[d][0];
int ty = j + xiang[d][1];
if(tx < 1 || ty < 1 || tx > n || ty > n || bar[tx][ty])
continue;//越界或者有障碍
add(u, pos(tx, ty), 1); //奇数位 --> 偶数位
}
}
else if((i+j)%2 == 0 && !bar[i][j])
add(pos(i, j), t, 1); //偶数位 --> 汇点
}
}
printf("%d
", n*n-m-Dinic());
return 0;
}