描述：
城堡是一个4×4的方格，为了保卫城堡，现需要在某些格子里修建一些堡垒。城堡中的某些格子是墙，其余格子都是空格，堡垒只能建在空格里，每个堡垒都可以向上下左右四个方向射击，如果两个堡垒在同一行或同一列，且中间没有墙相隔，则两个堡垒都会把对方打掉。问对于给定的一种状态，最多能够修建几个堡垒。
输入：
每个测例以一个整数n（1<=n<=4）开始，表示城堡的大小。接下来是n行字符每行n个，‘X’表示该位置是墙，‘.’表示该位置是空格。n等于0标志输入结束。
输出：
每个测例在单独的一行输出一个整数：最多修建堡垒的个数。
输入样例：
4
.X..
....
XX..
....
2
XX
.X
3
.X.
X.X
.X.
3
...
.XX
.XX
4
....
....
....
....
0
输出样例：
5
1
5
2
4
题解：
逐个地点的搜索是否能放堡垒，并利用一个回溯，求出所有结果。
代码：
#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
char a[][]={};
int maxn=,cur=; //maxn记录最终最优解，cur记录每一次最优解 bool iscanput(int x,int y,int n)
{
int r=x;
int c=y;
if(a[x][y]!='.')
return false;
while(y>=&&a[r][y]=='.')
{y--;}
if(y<||(y>=&&a[r][y]=='X')){
while(x>=&&a[x][c]=='.') x--;
if(x<||(x>=&&a[x][c]=='X')) return true;
}
return false;
} void Search(int i,int n)
{
int x=i/n;
int y=i%n;
if(i==n*n){
if(maxn<cur)
maxn=cur;
}
else{
if(iscanput(x,y,n)){ //看（x，y）是否能存放堡垒
a[x][y]='T';
cur++;
Search(i+,n);
cur--;
a[x][y]='.';
}
Search(i+,n);
}
} int main()
{
int n,i,j;
while(cin>>n,n){
maxn=;
cur=;
for(i=;i<n;i++)
for(j=;j<n;j++)
cin>>a[i][j];
Search(,n);
cout<<maxn<<endl;
}
return ;
}