时限：

1000ms 内存限制：10000K 总时限：3000ms

描述：

城堡是一个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
     
      char Arr[4][4]={
   0};int n,max=0;void checkmax(){    int sum=0;    for(int i=0;i
      
       max)//取置堡垒个数最多的        max=sum;}int canplace(int m)//判断是否能将Arr[m/n][m%n]置为堡垒{    int row,col,r,c;    row=m/n; col=m%n;//行//列    r=row;   c=col;  //保存行列值    if(Arr[row][col]=='X')  return 0; //是城墙，不能置为堡垒    while(col>=0 &&Arr[row][col]=='.')          col--;//对Arr[row][col]所在行的判断：Arr[row][col]同一行中只能是 出界或遇到城墙"X"或遇到堡垒"1"而结束    if(col<0 ||(col>=0 &&Arr[row][col]=='X'))    //Arr[row][col]同一行中出界或遇到城墙(同一行满足要求)而结束，才判断Arr[row][col]所在列    {        while(row>=0 &&Arr[row][c]=='.')  row--;//对Arr[row][col]所在列的判断：与行判断相同        if(row<0 ||(row>=0 &&Arr[row][c]=='X') )            return 1;    }    return 0;//Arr[row][col]所在行或列不满足要求}void search(int m){    if(m==n*n)        checkmax();    else    {   if(canplace(m))//满足将Arr[m/n][m%n]置为堡垒的条件        {  Arr[m/n][m%n]='1';//将Arr[m/n][m%n]置为堡垒           search(m+1);           Arr[m/n][m%n]='.';//恢复，不将Arr[m/n][m%n]置为堡垒             search(m+1);         }        else  search(m+1);//不将Arr[m/n][m%n]置为堡垒      }}int main(){   int i,j;   scanf("%d",&n);//输入城堡的大小n   getchar();///!!!!   while(n!=0)   {       for(i=0;i