题目大意：在给定的棋盘中，看最多可以放多少个棋子。放棋子规则：同一行同一列不可以有两个以上的棋子，除非中间有墙隔着。
阶梯思路：让每个棋子从不同的起点开始，然后往后遍历，每个起点都有对应可以放的棋子，取其中的最大值。遍历过程中如果是按先行再列的顺序遍历的话，如果当前已经便利完x，y；那么下一个遍历开始的位置就是x，y+ 1.注意判断完前面的位置之后，只需要从这个位置的后面开始判断，前面的不需要再判断了，棋子刚开始的起点的位置也是同样的道理。然后判断可以不可以放棋子，要从同一行和同一列两个方面判断。
如果在同一行（列）有已经放好的棋子（这里是用‘#’表示），就需要判断要放的位置和这个‘#’的位置中间有没有墙，有的话就可以放。如果对于同一行（列）的每一个都可以放的话就说明与行（列）不冲突。反之则反之。
#include<stdio.h>
#include<string.h>
const int N = 5;
int n, max;
char map[N][N];
void handle (int x, int y, int num) {
for (int i = x; i < n; i++ ) {
if ( i != x)
y = -1;
for (int l = y + 1; l < n; l++) {
if ( map[i][l] == ‘.‘) {
bool rf, cf;
rf = cf = 0;
int j, k;
for (j = 0; j < n; j++)
if (j != i && map[j][l] == ‘#‘) {
if ( j < i ) {
for (k = j + 1; k < i; k++)
if (map[k][l] == ‘X‘)
break;
if ( k == i )
break;
}else {
for (k = i + 1; k < j; k++)
if (map[k][l] == ‘X‘)
break;
if (k == j)
break;
}
}
if ( j == n)
cf = 1;
if (cf) {
for (j = 0; j < n; j++ )
if ( j != l && map[i][j] == ‘#‘) {
if ( j < l ) {
for ( k = j + 1; k < l; k++ )
if ( map[i][k] == ‘X‘)
break;
if ( k == l)
break;
}else {
for (k = l + 1; k < j; k++)
if (map[i][k] == ‘X‘)
break;
if (k == j)
break;
}
}
if (j == n)
rf = 1;
if (rf && cf) {
map[i][l] = ‘#‘;
handle(i, l, num + 1);
map[i][l] = ‘.‘;
}
}
}
}
}
if (num > max)
max = num;
}
int main () {
while (scanf("%d", &n), n) {
for (int i = 0; i < n; i++)
scanf("%s", map[i]);
max = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
if (map[i][j] == ‘.‘) {
map[i][j] = ‘#‘;
handle (i, j, 1);
map[i][j] = ‘.‘;
}
}
printf("%d\n", max);
}
return 0;
}
639 - Don't Get Rooked（搜索回溯）,布布扣,bubuko.com
原文：http://blog.csdn.net/u012997373/article/details/22915573