假设我们有一个拥有笔直街道的矩形城市，这个城市有n行，m列，每一个代表一条街或者一面墙。

  现在我们有一种有四个开口的碉堡，开口分别面向东，南，西，北四个方向，而且每个开口都有一把枪，我们假设那把枪射出的子弹有着特殊的能力：能够穿过开阔地段并且摧毁在路上的碉堡。另一方面，我们能建一种可以阻挡这种子弹的墙。

  我们的目标是在这个城市尽可能多的放置碉堡，同时保证它们之间互相不能摧毁。一种合法的配置是在相同的列和相同的行不能放置两个碉堡，除非它们之间有墙。在这个问题中我们将限制城市的大小规模，最大是4*4。

   接下来的五张图片我们将会描述一个大小相同的城市的不同配置方法。第一张图片是一个空的城市；第二个和第三个是合法的配置，第四个和第五个是不合法的配置

 

&nbsp;<img src="http://tk.hustoj.com:80/attached/image/20150404/20150404103911_74349.gif" alt="" /> 

<br />

<br />

对于这种城市模型，它的碉堡最大配置数为5，第二张图片表示的只是这种城市模型的一种配置方法，还有其他的配置方法，但是有可能达不到最大碉堡配置要求。

 

将会给你一系列的城市地图模型，你的任务是去计算这个城市模型最大能够放几个碉堡，当然是在合理的条件下啦。。。。。完成这个规划可以找王佩找棒棒糖，^­_^!

C++解答

#include<stdio.h>
#include<string.h>
char a[6][6];
int b[6][6];  
int all;
int n;
int  check(int x,int y)
{
	int xx=1;
	for (int i=x;i<n;i++)
	{
		if (b[i][y]==2&&i!=x) break;
		if (b[i][y]==1||b[x][y]==2) {xx=0;break;}
	}
	for (int i=x;i>=0;i--)
	{
		if (b[i][y]==2) break;
		if (b[i][y]==1) {xx=0;break;}
	}
	for (int i=y;i<n;i++)
	{
		if (b[x][i]==2&&i!=y) break;
		if (b[x][i]==1||b[x][y]==2) {xx=0;break;}
	}
	for (int i=y;i>=0;i--)
	{
		if (b[x][i]==2) break;
		if (b[x][i]==1) {xx=0;break;}
	}
	return xx;
}


void dfs(int kk,int x,int y)
{
	if (kk>all) all=kk;
	for (int i=y+1;i<n;i++)
	{
		//printf("(%d,%d)=%d\n",x,i,b[x][i]);
		if (check(x,i))
				{
					
					b[x][i]=1;
					dfs(kk+1,x,i);
					b[x][i]=0;
				}
	}
	for (int i=x+1;i<n;i++)
		{
			for (int j=0;j<n;j++)
			{
				//printf("(%d,%d)=%d\n",i,j,b[i][j]);
				if (check(i,j))
				{
					
					b[i][j]=1;
					dfs(kk+1,i,j);
					b[i][j]=0;
				}
			}
		}
}
int main()
{
	//freopen("F:\\QQDownlaod\\Laputa\\2015.4.4\\as\\data.in","r",stdin);
	//freopen("F:\\QQDownlaod\\Laputa\\2015.4.4\\as\\data.out","w",stdout);
	while(scanf("%d",&n)!=EOF&&n!=0)
	{
		getchar();
		memset(b,0,sizeof(b));
		for (int i=0;i<n;i++)
		{
			for (int j=0;j<n;j++)
			{
				scanf("%c",&a[i][j]);
				if (a[i][j]=='X') b[i][j]=2;
			}
			getchar();
		}
		all=0;
		for (int i=0;i<n;i++)
		{
			for (int j=0;j<n;j++)
			{
					//printf(">>   >>\n(%d,%d)=%d\n",i,j,b[i][j]);
				if (check(i,j))
				{
				
					b[i][j]=1;
					int sum=1;
					dfs(sum,i,j);
					b[i][j]=0;
				}
			}
		}
		printf("%d\n",all);
	}
	return 0;
}