AcWing 378. 骑士放置

2021-03-09 22:26

阅读：463

标签：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

上一篇：jsonp跨域访问数据，例：得到其他地址的天气接口

下一篇：WIN10连上了网络却无法上网

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：AcWing 378. 骑士放置
文章链接：http://soscw.com/essay/62470.html

亲，登录后才可以留言！

AcWing 378. 骑士放置

算法

思路

核心

最大匹配

代码

评论

热门文章

推荐文章

最新文章

置顶文章