比赛 |
4043级2023省选练习赛5 |
评测结果 |
AAAAAAAAAA |
题目名称 |
棋盘游戏 |
最终得分 |
100 |
用户昵称 |
yrtiop |
运行时间 |
0.024 s |
代码语言 |
C++ |
内存使用 |
2.52 MiB |
提交时间 |
2023-03-13 21:02:14 |
显示代码纯文本
#include <bits/stdc++.h>
#define pb emplace_back
const int maxn = 105;
const int maxm = 1e4 + 5;
std::vector<int> G[maxm];
int n,m,tot,t,idx[maxn][maxn],fx[4] = {0 , -1 , 0 , 1},fy[4] = {1 , 0 , -1 , 0},cur[maxm],lst[maxm];
char s[maxn][maxn];
std::pair<int,int> inv[maxm];
bool vis[maxm];
bool find(int u) {
if(vis[u])
return false;
for(auto& v : G[u]) {
if(vis[v]||v == t)
continue ;
vis[v] = true;
if(!cur[v]||find(cur[v])) {
cur[v] = u;
cur[u] = v;
return true;
}
}
return false;
}
void dfs(int u) {
if(vis[u])
return ;
vis[u] = true;
for(auto& v : G[u])
if(cur[v])
dfs(cur[v]);
return ;
}
int main() {
freopen("qpyx.in","r",stdin);
freopen("qpyx.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i = 1;i <= n;++ i)
scanf("%s",s[i] + 1);
int ans = 0,cnt = 0;
for(int i = 1;i <= n;++ i)
for(int j = 1;j <= m;++ j)
if(s[i][j] != '#')
idx[i][j] = ++ tot,inv[tot] = {i , j};
for(int i = 1;i <= n;++ i)
for(int j = 1;j <= m;++ j)
for(int k = 0;k < 4;++ k) {
int x = fx[k] + i,y = fy[k] + j;
if(x >= 1&&x <= n&&y >= 1&&y <= m&&s[i][j] != '#'&&s[x][y] != '#')
G[idx[i][j]].pb(idx[x][y]);
}
t = 0;
for(int i = 1;i <= tot;++ i) {
for(int j = 1;j <= tot;++ j)
vis[j] = false;
auto& [x , y] = inv[i];
if((x + y) & 1)
continue ;
if(find(i))
++ ans;
}
std::vector<std::pair<int,int> > output;
for(int j = 1;j <= tot;++ j)
vis[j] = false;
for(int i = 1;i <= tot;++ i) {
if(!cur[i])
dfs(i);
}
for(int i = 1;i <= tot;++ i)
if(vis[i])
output.pb(inv[i]);
printf("%d\n",output.size());
for(auto& [x , y] : output)
printf("%d %d\n",x,y);
return 0;
}