记录编号	301279	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2011]兔兔与蛋蛋游戏	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	0.040 s
提交时间	2016-08-30 22:25:02	内存使用	0.84 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N=1610;
const int M=15010;
int cnt,cntX,cntO;
int fir[N],to[M],nxt[M];
int match[N],vis[N],ban[N],id[50][50],ans[100010];
char map[50][50];
int n,m,px,py;
int tx[4]={0,1,0,-1};
int ty[4]={1,0,-1,0};
void addedge(int a,int b){
	nxt[++cnt]=fir[a];to[fir[a]=cnt]=b;
}

bool DFS(int x){
	for(int i=fir[x];i;i=nxt[i])
		if(!vis[to[i]]&&!ban[to[i]]){vis[to[i]]=1;
			if(!match[to[i]]||DFS(match[to[i]]))
				{match[match[to[i]]=x]=to[i];return true;}
		}
	return false;	
}

int main(){
	freopen("noi2011_game.in","r",stdin);
	freopen("noi2011_game.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%s",map[i]+1);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			if(map[i][j]=='.')
				map[i][j]='X',px=i,py=j;
			if(map[i][j]=='O')
				id[i][j]=++cntO;
			else if(map[i][j]=='X')
				id[i][j]=++cntX;	
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(map[i][j]=='O')
				id[i][j]+=cntX;
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)if(id[i][j]){
			for(int k=0;k<4;k++){
				int gx=tx[k]+i,gy=ty[k]+j;
				if(map[gx][gy]!=map[i][j])
					addedge(id[i][j],id[gx][gy]);
			}
		}
	for(int i=1;i<=cntX;i++)if(!match[i])
		{memset(vis,0,sizeof(vis));DFS(i);}
	
	int k;scanf("%d",&k);
	for(int i=1;i<=2*k;i++){
		int x;ban[x=id[px][py]]=1;
		if(match[x]){int y=match[x];
			memset(vis,0,sizeof(vis));
			match[x]=match[y]=0;
			ans[i]=DFS(y)^1;
		}
		scanf("%d%d",&px,&py);
	}
	int ret=0;
	for(int i=1;i<=k;i++)
		ret+=ans[i*2]&ans[i*2-1];
	printf("%d\n",ret);
	for(int i=1;i<=k;i++)
		if(ans[i*2]&ans[i*2-1])
			printf("%d\n",i);
	return 0;
}