30分
查看原帖
30分
381706
EXnoLph楼主2022/2/14 19:05

30分wa

//#define res register int
#include <bits/stdc++.h>
using namespace std;
const int inf1=100005;
const int inf2=2005;
int to[inf1],nxt[inf1],head[inf1],top;
int vis[inf1*8],use[inf1*8];
int mp[inf2][inf2];
int n,m;
int sum,sum2;
int ans;
int cnt[inf1];
void add(int now,int tow){
	to[++top]=tow;
	nxt[top]=head[now];
	head[now]=top;
}
bool dfs(int x){
	for (int i=head[x];i!=0;i=nxt[i]){
		int ver=to[i];
		if(!vis[ver]){
			vis[ver]=1;
			if(use[ver]==0||dfs(use[ver])){
				use[ver]=x;
				return 1;
			}
		}
	}
	return 0;
}
void first(int x,int y){
	int tot=0;
	for(int i=1;i<=x;i++){
		for(int j=1;j<=y;j++){
			mp[i][j]=++tot;
		}
	}
}
void find(int x){
	if(vis[x]!=0){return;}

	vis[x]=1;
	for(int i=head[x];i!=0;i=nxt[i]){
		int ver=to[i];
		if(use[ver]!=0&&vis[use[ver]]!=1){find(use[ver]);}
	}
}
int main(){
	cin>>n>>m;
	char tmp;
	first(n,m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>tmp;
			if(tmp!='#'){
				sum++;
				if(mp[i][j]%2){
					cnt[++sum2]=mp[i][j];
				}
				if(mp[i][j-1]!=0){add(mp[i][j],mp[i][j-1]);add(mp[i][j-1],mp[i][j]);}
				if(mp[i-1][j]!=0){add(mp[i][j],mp[i-1][j]);add(mp[i-1][j],mp[i][j]);}
			}
			else{
				mp[i][j]=0;
			}
		}
	}
	for(int i=1;i<=sum2;i++){
		if(dfs(cnt[i])){
		    ans+=2;
		}
		memset(vis,0,sizeof(vis));
	}
	if(ans==sum)cout<<"LOSE";
	else{
		cout<<"WIN"<<endl;
		for(int i=1;i<=n*m;i++){
			if(use[i]!=0){
				use[use[i]]=i;
			}
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(mp[i][j]!=0&&use[i*nn+j]==0)						{find(i*n-n+j);}
			}
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(vis[i*n-n+j]!=0){
					cout<<i<<" "<<j<<endl;
				}
			}
		}
	}
}
2022/2/14 19:05
加载中...