UVa 639 Don't Get Rooked

题目：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=580
最多16个格，2^16=65536可以枚举完，而且很多都是可以剪枝的，用dfs枚举就可以。
要注意的是如果在dfs之前用vis数组标记放下了“车”，那么要在dfs之后清除掉。

#include<cstdio>
#include<cstring>
#define clear(x) (memset(x,0,sizeof(x)))

char map[4][4];
bool vis[4][4];
int n,max;

void getnext(int x,int y,int &nextx,int &nexty)
{
	if(x<n-1)
	{
		nextx=x+1;
		nexty=y;
	}
	else if(y<n-1)
	{
		nextx=0;
		nexty=y+1;
	}
	else
		nextx=nexty=-1;//标志已经到最后了
}
bool canputdown(int x,int y)
{
	if(map[x][y]=='X') return 0;
	int i;
	for(i=x-1;i>=0&&map[i][y]=='.';i--)
		if(vis[i][y]) return 0;
	for(i=y-1;i>=0&&map[x][i]=='.';i--)
		if(vis[x][i]) return 0;
	return 1;
}
void dfs(int x,int y)
{
	if(x==-1&&y==-1)
	{
		int cnt=0;
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				if(vis[i][j]) cnt++;
		if(cnt>max) max=cnt;
		return;
	}
	int nextx,nexty;
	getnext(x,y,nextx,nexty);
	if(canputdown(x,y))//如果能放下
	{
		vis[x][y]=1;//放
		dfs(nextx,nexty);
		vis[x][y]=0;//不放
		dfs(nextx,nexty);
	}
	else
		dfs(nextx,nexty);
}
int main()
{
	//freopen("in.txt","r",stdin);
	int i;
	while(scanf("%d",&n)&&n)
	{
		for(i=0;i<n;i++)
			scanf("%s",map[i]);
		max=0;
		clear(vis);
		dfs(0,0);
		printf("%d\n",max);
	}
	return 0;
}