这种两个人轮流走,不能走 走过的格子的大都是二分图博弈。。。

#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define pii pair<int, int>
#define y1 skldjfskldjg
#define y2 skldfjsklejg using namespace std; const int N = + ;
const int M = 1e5 + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 +; int n, m, tot, hs[N][N], match[N * N], f[N * N], ans[N * N];
int dx[] = {, }, dy[] = {, };
bool vis[N * N];
vector<int> edge[N * N];
char s[N][N]; int path(int u) {
for(int i = ; i < edge[u].size(); i++) {
int v = edge[u][i];
if(!vis[v]) {
vis[v] = true;
if(match[v] == - || path(match[v])) {
match[v] = u;
return ;
}
}
}
return ;
} void work(int u) {
if(ans[u]) return;
ans[u] = ;
for(int i = ; i < edge[u].size(); i++) {
int v = edge[u][i];
if(match[v] != -) work(match[v]);
}
} int main() {
memset(match, -, sizeof(match));
scanf("%d%d", &n, &m);
for(int i = ; i <= n; i++) scanf("%s", s[i] + ); for(int i = ; i <= n; i++) {
for(int j = ; j <= m; j++) {
if(s[i][j] == '#') continue;
hs[i][j] = ++tot;
f[hs[i][j]] = (i ^ j) & ;
}
} for(int i = ; i <= n; i++) {
for(int j = ; j <= m; j++) {
if(s[i][j] == '#') continue;
for(int k = ; k < ; k++) {
int x = i + dx[k], y = j + dy[k];
if(hs[x][y]) {
edge[hs[i][j]].push_back(hs[x][y]);
edge[hs[x][y]].push_back(hs[i][j]);
}
} }
} int cnt = ;
for(int i = ; i <= tot; i++) {
if(f[i]) {
memset(vis, , sizeof(vis));
if(path(i)) cnt++;
}
}
if( * cnt == tot) {
puts("LOSE");
} else {
puts("WIN");
for(int i = ; i <= tot; i++) {
if(match[i] != -) match[match[i]] = i;
}
for(int i = ; i <= tot; i++) {
if(match[i] == -) work(i);
} for(int i = ; i <= n; i++) {
for(int j = ; j <= m; j++) {
if(ans[hs[i][j]]) printf("%d %d\n", i, j);
}
}
}
return ;
} /*
*/

最新文章

  1. (转)SVN服务器搭建和使用(二)
  2. 第三波假期干货——webstrom工具栏图标
  3. Linux - 常用Shell命令
  4. css加阴影
  5. JS&amp;CSS文件请求合并及压缩处理研究(一)
  6. 深入理解Java String#intern() 内存模型
  7. Lucene学习笔记: 五,Lucene搜索过程解析
  8. SNMP协议总结
  9. 2.2.5 NIO.2 Path 和 Java 已有的 File 类
  10. setTimeout()与setInterval() 问题
  11. 分享几个有意思的css js工具网站
  12. flask 手机号码正则匹配的简单操作
  13. 【Windows】+ windows下在某一文件夹下按“shift+鼠标右键”打开CMD窗口
  14. Mac 下 软件安装路径查看 命令: Which, 估计Linux 也是
  15. Java 容器之 Connection栈队列及一些常用
  16. 在ASP.NET Core上实施每个租户策略的数据库
  17. Android几行代码实现监听微信聊天
  18. MySQL 5.6 Replication 复制 FAQ
  19. 九度 1494:Dota(完全背包)
  20. Discoverer Table

热门文章

  1. DOM案例五星评分控件
  2. UBOOT启动内核过程
  3. [技巧篇]14.据说SSH框架需要的监听器,IntrospectorCleanupListener
  4. matlab向量的排序(自写函数)
  5. nodejs formidable混合表单提交
  6. 什么叫TLD、gTLD、nTLD、ccTLD、iTLD 以及几者之间的关系
  7. 51Nod 1062 序列中最大的数 | 简单DP
  8. [Luogu 3958] NOIP2017 D2T1 奶酪
  9. 微信公众号支付开发全过程(Java 版)
  10. 程序员你为什么这么累? - Controller规范