# 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 int nextInt() throws IOException
{
while(leave==0)
{
leave=st.countTokens();
}
int a=Integer.parseInt(st.nextToken());
leave--;
return a;
}
static String nextLine() throws IOException
{
}
}
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());
}
}
}

This entry was posted in poj. Bookmark the permalink.