玄关求助 80 分!!!
查看原帖
玄关求助 80 分!!!
866154
fcy20180201楼主2024/6/7 21:54
#include<bits/stdc++.h>
using namespace std;
int n,m,bk[10005],dx[]={1,0,-1,0},dy[]={0,1,0,-1},fst[10005],tot; 
char s[105][105];
vector<int>con[10005];
bool ans,mt[10005],vis[10005],vis2[10005];
bool dfs(int u){
	for(int v:con[u])if(!vis[v]){
		vis[v]=true;
		if(!bk[v] || dfs(bk[v])){bk[v]=u;return true;}
	}
	return false;
}
void dfs2(int u){
	vis[u]=ans=true;
	for(int v:con[u])if(!vis2[v] && bk[v])vis2[v]=true,dfs2(bk[v]);
	return ;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++)scanf("%s",s[i]);
	for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(s[i][j]=='.'){
		for(int k=0;k<4;k++){
			int nx=i+dx[k],ny=j+dy[k];
			if(nx>=0 && nx<n && ny>=0 && ny<m && s[nx][ny]=='.')con[i*m+j].push_back(nx*m+ny);
		}
		if(!(i+j&1))fst[++tot]=i*m+j;
	}
	for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(s[i][j]=='.' && (i+j)&1){
		for(int k=1;k<=tot;k++)vis[fst[k]]=false;
		dfs(i*m+j);
	}
	for(int i=0;i<n*m;i++)if(bk[i])mt[i]=mt[bk[i]]=true,bk[bk[i]]=i;
	memset(vis,0,sizeof(vis));
	for(int i=0;i<n*m;i++)if(s[i/m][i%m]=='.' && !vis[i] && !mt[i])dfs2(i);
	puts(ans?"WIN":"LOSE");
	for(int i=0;i<n*m;i++)if(vis[i])printf("%d %d\n",i/m+1,i%m+1);
	return 0;
}

2024/6/7 21:54
加载中...