## codechef： BINARY, Binary Movements

Judge_Cheung 2019-05-15 22:35:00 阅读数:24 评论数:0 收藏数:0

``````//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
#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;
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){
}
bool dfs(int u){ vis[u]=tim;
go(u) if(vis[v]^tim){ vis[v]=tim;
} return 0;
}
int main(){
fp(i,1,n){
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);
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]])
if(mp[i-1][j+1]&&!now[id[i-1][j+1]])
if(mp[i+1][j-1]&&!now[id[i+1][j-1]])
if(mp[i+1][j+1]&&!now[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
...

*/

``````