题目大意：有一个4*4的城市，其中一些格子有墙（X表示墙），在剩余的区域放置碉堡。子弹不能穿透墙壁。问最多可以放置几个碉堡，保证它们不会相互误伤。

解法：从左上的顶点开始遍历，如果这个点不是墙，做深度优先搜索，算出这种情况下的最多碉堡数。每做一次DFS，更新一次最大值。

参考代码：

#include<iostream>

#include<cstdio>

#include<string.h>

using namespace std;

char city[6][6];

int i,j,n,ans,maxi,visited[6][6];

void DSF();

int find(int x,int y);

int main(){

	while(cin>>n&&n){

		memset(city,'X',sizeof(city));		//this is included in <string.h>

		memset(visited,0,sizeof(visited));

		ans=maxi=0;

		getchar();		//this is included in <cstdio.h>

		for(i=1;i<=n;i++){

			for(j=1;j<=n;j++)

				cin>>city[i][j];

			getchar();

		}

		DSF();

		cout<<ans<<endl;

	}

	return 0;

}

void DSF(){

	int r,c;

	if(ans<maxi) ans=maxi;

	for(r=1;r<=n;r++){			//intially it is a loop to sweep all the blocks in the city

		for(c=1;c<=n;c++){

			if(!visited[r][c]&&city[r][c]!='X'){

				if(find(r,c)){		// check if can put a castle in this block

					visited[r][c]=1;	//put a castle and the number of castle increase by one

					maxi++;

					DSF();		//continue search, similar to pushing this block into stack

					visited[r][c]=0;	//return and number of castle minus one

					maxi--;

				}

			}

		}

	}

}

int find(int x,int y){

	int i;

	for(i=x-1;i>0;i++){		//check if there is castle in front, from the nearest to furthest

		if(visited[i][y]==1) return 0;

		if(city[i][y]=='X') break;	//if there has a wall, no problem, continue to next direction

	}

	for(i=y-1;i>0;i++){				//left

		if(visited[x][i]==1) return 0;

		if(city[x][i]=='X') break;

	}

	for(i=x+1;i<=n;i++){			//back

		if(visited[i][y]==1) return 0;

		if(city[i][y]=='X') break;

	}

	for(i=y+1;i<=n;i++){			//right

		if(visited[x][i]==1) return 0;

		if(city[x][i]=='X') break;

	}

	return 1;

}