比赛 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;
}