codechef： BINARY, Binary Movements

非常有毛病的一道题，我一个一个读字符死活过不去，改成整行整行读就 A 了...

做法就是...最小点覆盖...

我们发现可以把一个点向上跳看做被吃掉了，然后最顶层的点是无法向上跳所以不能被吃掉，然后被吃掉的点相连的边都会被删除...

这样转换完模型之后特判两下用二分图匹配就好了（因为这里的环最多是四元，或者说是偶数长度环...）

注意顶部的点必须要特判...因为顶部的点无法删除...

//by Judge

#include<cstdio>

#include<cstring>

#include<iostream>

#define Rg register

#define fp(i,a,b) for(Rg int i=(a),I=(b)+1;i<I;++i)

#define fd(i,a,b) for(Rg int i=(a),I=(b)-1;i>I;--i)

#define go(u) for(Rg int i=head[u],v=e[i].to;i;v=e[i=e[i].nxt].to)

using namespace std;

const int N=103;

const int M=2e4+3;

typedef int MP[N][N];

typedef int arr[M];

#ifndef Judge

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

#endif

char buf[1<<21],*p1=buf,*p2=buf;

inline int read(){ int x=0,f=1; char c=getchar();

	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;

	for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f;

} inline int cread(int* s){ Rg int len=0; Rg char ch;

	while((ch=getchar())!='O'&&ch!='.');

	for(s[++len]=ch=='O';(ch=getchar())=='O'||ch=='.';s[++len]=ch=='O');

	return s[len+1]='\0',len;

} char sr[1<<21],z[20];int C=-1,Z;

inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}

inline void print(Rg int x,Rg char chr=' '){

    if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;

    while(z[++Z]=x%10+48,x/=10);

    while(sr[++C]=z[Z],--Z);sr[++C]=chr;

} int n,cnt,tim,res,pat,head[M<<2];

arr px,py,to,vis,bl,now,ok; MP id,mp;

struct Edge{ int to,nxt; }e[M];

inline void add(int u,int v){

	e[++pat]=(Edge){v,head[u]},head[u]=pat;

}

bool dfs(int u){ vis[u]=tim;

	go(u) if(vis[v]^tim){ vis[v]=tim;

		if(!to[v]||dfs(to[v])) return to[v]=u,1;

	} return 0;

}

int main(){

	fp(i,1,read()){ n=read(),cnt=pat=res=0;

		fp(i,1,n){

			cread(mp[i]);

			fp(j,1,n) if(mp[i][j])

				id[i][j]=++cnt,

				px[cnt]=i,py[cnt]=j,

				bl[cnt]=(i&1);

		}

		fp(i,1,n+1) mp[n+1][i]=0;

		memset(ok,0,(cnt+2)<<2);

		memset(to,0,(cnt+2)<<2);

		memset(vis,0,(cnt+2)<<2);

		memset(now,0,(cnt+2)<<2);

		memset(head,0,(cnt+2)<<2);

		fp(i,1,n) fp(j,1,n)

			if(mp[i][j]&&!mp[i-1][j-1]&&!mp[i-1][j+1]){

				now[id[i][j]]=1;

				if(mp[i+1][j+1]) now[id[i+1][j+1]]=2;

				if(mp[i+1][j-1]) now[id[i+1][j-1]]=2;

			}

		fp(i,1,cnt) res+=(now[i]==2);

		for(Rg int i=1;i<=n;i+=2) fp(j,1,n)

			if(mp[i][j]&&!now[id[i][j]]){

				if(mp[i-1][j-1]&&!now[id[i-1][j-1]])

					add(id[i][j],id[i-1][j-1]);

				if(mp[i-1][j+1]&&!now[id[i-1][j+1]])

					add(id[i][j],id[i-1][j+1]);

				if(mp[i+1][j-1]&&!now[id[i+1][j-1]])

					add(id[i][j],id[i+1][j-1]);

				if(mp[i+1][j+1]&&!now[id[i+1][j+1]])

					add(id[i][j],id[i+1][j+1]);

			}

		tim=0;

		fp(i,1,cnt) if(!now[i])

			if(++tim&&dfs(i)) ++res;

		fp(i,1,cnt) if(to[i]) ok[to[i]]=1;

		++tim;

		fp(i,1,cnt) if(!now[i]&&bl[i]&&!ok[i]) dfs(i);

		fp(i,1,cnt) if(!now[i]&&bl[i]&&vis[i]^tim) now[i]=2;

		fp(i,1,cnt) if(!now[i]&&!bl[i]&&vis[i]==tim) now[i]=2;

		print(res,'\n');

		fd(i,cnt,1) if(now[i]&2){

			Rg int x=px[i],y=py[i]; print(x),print(y);

			sr[++C]=mp[x-1][y-1]?'L':'R',sr[++C]='\n';

		}

	} return Ot(),0;

}

/*

2

7

OOOOOOO

OOOOOOO

OOOOOOO

OOOOOOO

OOOOOOO

OOOOOOO

OOOOOOO

3

.O.

O.O

...

*/

巴特西

codechef： BINARY, Binary Movements

最新文章

热门文章