AcWing 378. 骑士放置
2021-03-09 22:26
阅读：515
标签：tin size set end 二分图 商业 int 最小 不同
算法
二分图+最小独立集
思路
在日字形内两点连边（1），必处于不同色格子（0）。为二分图。要互不相扰，求最大独立集。
核心
最大匹配
bool dfs(int x, int y) {
for (int i = 0; i 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;
}
就加了个范围判定。
代码
#include#include #include #include using namespace std; int n, m, t, ans, fx[105][105], fy[105][105]; bool a[105][105], v[105][105]; 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 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 = 1; i > x >> y; a[x][y] = 1; } for (int i = 1; i
AcWing 378. 骑士放置
标签：tin size set end 二分图 商业 int 最小 不同
原文地址：https://www.cnblogs.com/ruanmowen/p/12725502.html
评论
亲，登录后才可以留言！