非常有毛病的一道题，我一个一个读字符死活过不去，改成整行整行读就 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
原文：https://www.cnblogs.com/Judge/p/10872661.html