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

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<deque>
#include<iomanip>
#include<cstring>
#include<stack>
#include<vector>
#include<queue>
#include<fstream>
using namespace std;
const int SIZEN=50,SIZEG=1700;
int n,m;//棋盘大小
int K;
int N;//图的大小(总点数)
char board[SIZEN][SIZEN]={0};
//点(x,y)的序号:x*m+y,其中x,y>=0
vector<int> c[SIZEG];//邻接表
bool visit[SIZEG]={0};
int match[SIZEG]={0};
bool une[SIZEG]={0};
class POINT{
public:
	int x,y;
}space;
bool findpath(int x){
	if(visit[x]||une[x]) return false;
	int i,v;
	for(i=0;i<c[x].size();i++){
		v=c[x][i];
		if(visit[v]||une[v]) continue;
		visit[v]=true;
		if(match[v]==-1||findpath(match[v])){
			match[v]=x;
			match[x]=v;
			return true;
		}
	}
	return false;
}
int hung(void){
	int i,ans=0;
	for(i=0;i<N;i++) if(findpath(i)) ans++;
	return ans;
}
deque<int> wrong;
void write(void){
	printf("%d\n",wrong.size());
	if(wrong.empty()) return;
	int i;
	for(i=0;i<wrong.size();i++) printf("%d\n",wrong[i]);
	printf("\n");
}
int getid(int x,int y){
	return x*m+y;
}
void del(POINT space){
	int now=getid(space.x,space.y);
	une[now]=true;
}
void res(POINT space){
	int now=getid(space.x,space.y);
	une[now]=false;
}
bool swin(bool rabbit,int step,POINT loc){
	POINT op;
	del(loc);
	scanf("%d%d",&op.x,&op.y);
	op.x--,op.y--;
	bool flag;
	if(step==2*K){
		res(loc);
		memset(visit,0,sizeof(visit));
		hung();
		return true;
	}
	flag=swin(!rabbit,step+1,op);
	res(loc);
	memset(visit,0,sizeof(visit));
	if(findpath(getid(loc.x,loc.y))){
		if(rabbit&&flag) wrong.push_front((step+1)/2);
		return true;
	}
	return false;
}
queue<POINT> Q;
void addedge(int x,int y){
	c[x].push_back(y);
}
void BFS(void){//这个BFS其实可以用更为高♂雅的方式写的
	Q.push(space);
	visit[getid(space.x,space.y)]=false;
	POINT fr;
	int now,nx,ny,temp;
	while(!Q.empty()){
		fr=Q.front();Q.pop();
		nx=fr.x,ny=fr.y;
		now=getid(nx,ny);
		char ch=board[nx][ny];
		if(nx<n-1&&board[nx+1][ny]!=ch){
			temp=getid(nx+1,ny);
			addedge(now,temp);
			if(visit[temp]){
				visit[temp]=false;
				Q.push((POINT){nx+1,ny});
			}
		}
		if(nx>0&&board[nx-1][ny]!=ch){
			temp=getid(nx-1,ny);
			addedge(now,temp);
			if(visit[temp]){
				visit[temp]=false;
				Q.push((POINT){nx-1,ny});
			}
		}
		if(ny<m-1&&board[nx][ny+1]!=ch){
			temp=getid(nx,ny+1);
			addedge(now,temp);
			if(visit[temp]){
				visit[temp]=false;
				Q.push((POINT){nx,ny+1});
			}
		}
		if(ny>0&&board[nx][ny-1]!=ch){
			temp=getid(nx,ny-1);
			addedge(now,temp);
			if(visit[temp]){
				visit[temp]=false;
				Q.push((POINT){nx,ny-1});
			}
		}
	}
}
void read(void){
	scanf("%d%d",&n,&m);
	N=n*m;
	int i,j;
	for(i=0;i<n;i++){
		getchar();
		for(j=0;j<m;j++){
			scanf("%c",&board[i][j]);
			if(board[i][j]=='.'){
				space.x=i;
				space.y=j;
				board[i][j]='X';
			}
		}
	}
	scanf("%d",&K);
	memset(visit,1,sizeof(visit));
	memset(match,-1,sizeof(match));
	memset(une,0,sizeof(une));
}
int main(){
	freopen("noi2011_game.in","r",stdin);
	freopen("noi2011_game.out","w",stdout);
	read();
	BFS();
	swin(true,1,space);
	write();
	return 0;
}
//若起点不在某个最大匹配中,先手必败
//若起点在所有最大匹配中,先手必胜