记录编号	61603	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2011]兔兔与蛋蛋游戏	最终得分	100
用户昵称	CyaNide-	是否通过	通过
代码语言	C++	运行时间	0.015 s
提交时间	2013-06-12 20:42:19	内存使用	3.22 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=41;
const int maxt=1601;
struct edge {int v,next;} e[maxt<<1];
int num[maxn][maxn],h[maxt],q[maxt],a[maxt],b[maxt],ans[maxt],c[maxt],*l,*r; //Swap the address
int n,m,k,t,t0,x0,y0,x,y,tot;
bool f[maxn][maxn],vis[maxt],del[maxt];
char s[maxn][maxn];

void addedge(int u,int v){
	e[++tot].v=v; e[tot].next=h[u]; h[u]=tot;
	e[++tot].v=u; e[tot].next=h[v]; h[v]=tot;
}

bool DFS(int u){
	for (int i=h[u];i;i=e[i].next){
		int v=e[i].v;
		if (!del[v] && !vis[v]){
			vis[v]=true; q[++t0]=v;
			if (!l[v] || DFS(l[v])) {l[v]=u; r[u]=v; return true;}
		}
	}
	return false;
}

bool confirm(int u){
	q[++t0]=u; vis[u]=true;
	if (!r[u]) return false; int v=r[u];
	for (int i=h[v];i;i=e[i].next){
		int u0=e[i].v;
		if (!del[u0] && !vis[u0] && !confirm(u0)) return false;
	}
	return true;
}

bool check(int u){
	if (r[u]==0) return false;
	t0=0; bool flag=confirm(u);
	for (int i=1;i<=t0;i++) vis[q[i]]=false;
	return flag;
}

void remove(int u){
	del[u]=true; int v=r[u];
	if (v) l[v]=r[u]=0; swap(l,r);
	if (v){
		t0=0; DFS(v);
		for (int i=1;i<=t0;i++) vis[q[i]]=false;
	}
}

int main(){
	freopen("noi2011_game.in","r",stdin);
	freopen("noi2011_game.out","w",stdout);
	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]=='.') {x0=i; y0=j; break;}
	f[x0][y0]=true; num[x0][y0]=1;
	t=1; c[1]=0;
	for (int i=0;i<n;i++)
		for (int j=0;j<m;j++)
			if (i!=x0 || j!=y0){
				if (s[i][j]=='X' && ((i+j)&1)==((x0+y0)&1)) {num[i][j]=++t; f[i][j]=true; c[t]=0;}
				if (s[i][j]=='O' && ((i+j)&1)!=((x0+y0)&1)) {num[i][j]=++t; f[i][j]=true; c[t]=1;}
			}
	tot=0;
	for (int i=0;i<n;i++)
		for (int j=0;j<m;j++) if (f[i][j]){
			if (f[i+1][j]) addedge(num[i][j],num[i+1][j]);
			if (f[i][j+1]) addedge(num[i][j],num[i][j+1]);
		}
	scanf("%d",&k); l=a; r=b;
	for (int i=1;i<=t;i++) if (c[i]==0){
		t0=0; DFS(i);
		for (int j=1;j<=t0;j++) vis[q[j]]=false;
	}
	int u=num[x0][y0];
	for (int i=1;i<=k;i++){
		bool f1=check(u); remove(u);
		scanf("%d%d",&x,&y); u=num[x-1][y-1]; //Be careful of relative coordination
		bool f2=check(u); remove(u);
		scanf("%d%d",&x,&y); u=num[x-1][y-1];
		if (f1 && f2) ans[++ans[0]]=i;
	}
	printf("%d\n",ans[0]);
	for (int i=1;i<=ans[0];i++) printf("%d\n",ans[i]);
	return 0;
}