2013
11-09

Don’t Get Rooked

In chess, the rook is a piece that can move any number of squares vertically or horizontally. In this problem we will consider small chess boards (at most 4×4) that can also contain walls through which rooks cannot move. The goal is to place as many rooks on a board as possible so that no two can capture each other. A configuration of rooks is legal provided that no two rooks are on the same horizontal row or vertical column unless there is at least one wall separating them.

The following image shows five pictures of the same board. The first picture is the empty board, the second and third pictures show legal configurations, and the fourth and fifth pictures show illegal configurations. For this board, the maximum number of rooks in a legal configuration is 5; the second picture shows one way to do it, but there are several other ways.

Your task is to write a program that, given a description of a board, calculates the maximum number of rooks that can be placed on the board in a legal configuration.

The input contains one or more board descriptions, followed by a line containing the number 0 that signals the end of the file. Each board description begins with a line containing a positive integer n that is the size of the board; n will be at most 4. The next n lines each describe one row of the board, with a ‘.’ indicating an open space and an uppercase ‘X’ indicating a wall. There are no spaces in the input.

For each test case, output one line containing the maximum number of rooks that can be placed on the board in a legal configuration.

4
.X..
....
XX..
....
2
XX
.X
3
.X.
X.X
.X.
3
...
.XX
.XX
4
....
....
....
....
0


5
1
5
2
4

//* @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());
}
}
}

1. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮