Poj Solution 1315

http://poj.org/problem?id=1315

//* @author: 
import java.io.*;
import java.util.StringTokenizer;

/*����,ÿ���Wall��λ����}�����,��rook����,���Թ�����Ӽ��ռ���,���ݵõ����Էŵ����rook��
 *���ռ���Ϊһ�ö�����,������nΪ16,ʱ�临�Ӷ�ΪO(2^n)<=65536,�����㷨����
 *�����Լ�������rook����ֱ��ˮƽ�����Ҵ�λ�ò�Ϊǽ..
 */

class cin
{
static int leave=0;
static StringTokenizer st;
static BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
static int nextInt() throws IOException
{
   while(leave==0)
   {
    st=new StringTokenizer(in.readLine());
    leave=st.countTokens();
   }
   int a=Integer.parseInt(st.nextToken());
   leave--;
   return a;
}
static String nextLine() throws IOException
{
   return in.readLine();
}
}
class Chess
{
char board[][];
int best,n,now,max;

void set(char b[][],int num)
{
   board=b;
   n=num;
   best=0;
   now=0;
   max=n*n;
}

boolean place(int x,int y)   //Լ����
{
   int i;
   if(board[x][y]=='X')return false;
   i=x-1;
   while(i>=0) //������rook
   {
    if(board[i][y]=='r')return false;
    if(board[i][y]=='X')break;
    i--;
   }
   i=x+1;
   while(i< n) //������rook
   {
    if(board[i][y]=='r')return false;
    if(board[i][y]=='X')break;
    i++;
   }
   i=y-1;
   while(i>=0) //������rook
   {
    if(board[x][i]=='r')return false;
    if(board[x][i]=='X')break;
    i--;
   }
   i=y+1;
   while(i< n) //������rook
   {
    if(board[i][y]=='r')return false;
    if(board[i][y]=='X')break;
    i++;
   }
   return true;
}

void backTrack(int t) //����
{
   if(t==max)
   {
    if(now>best)best=now;
   }
   else 
   {
    if(max-t+1< best-now)return;
    int i=t/n,j=t%n;
    if(place(i,j))
    {
     now++;
     board[i][j]='r';
     backTrack(t+1);
     board[i][j]='.';
     now--;
    }
    backTrack(t+1);
   }
}
int outSum()
{
   backTrack(0);
   return best;
}
}

public class Main {
    public static void main(String args[]) throws IOException
    {
    char board[][]=new char[4][4];
    String temp;
    Chess data=new Chess();
    int n,i,j;
    while(true)
    {
       n=cin.nextInt();
       if(n==0)break;
       for(i=0;i< n;i++)
       {
        temp=cin.nextLine();
        for(j=0;j< n;j++)
         board[i][j]=temp.charAt(j);
       }
       data.set(board,n);
       System.out.println(data.outSum());
    }
    }
}