题目：跟N皇后问题一样，不考虑对角冲突，但考虑墙的存在，只要中间有墙就不会

#include    
  
const int maxn = 5;  
char map[maxn][maxn];  
int ans, n;  
  
bool isok(int x, int y) {  
    for (int i = x + 1; i <= n && map[i][y] != 'X'; i++)  
        if(map[i][y] == '0')  
            return false;  
    for (int i = x - 1; i >= 1 && map[i][y] != 'X'; i--)  
        if(map[i][y] == '0')  
            return false;  
    for (int i = y; i <= n && map[x][i] != 'X'; i++)  
        if (map[x][i] == '0')  
            return false;  
    for (int i = y - 1; i >= 1 && map[x][i] != 'X'; i--)  
        if (map[x][i] == '0')  
            return false;  
    return true;  
}  
  
void dfs(int x, int y, int p) {  
    for (int i = 1; i <= n; i++)  
        for (int j = 1; j <= n; j++)  
            if (map[i][j] == '.' && isok(i, j)) {  
                map[i][j] = '0';  
                dfs(i, j, p + 1);  
                map[i][j] = '.';  
            }  
    if (ans < p)  
        ans = p;  
}  
  
int main() {  
    while (scanf("%d", &n) && n) {  
        gets(map[0]);  
        for (int i = 1; i <= n; i++)  
            gets(map[i] + 1);  
        ans = 0;  
        dfs(1, 1, 0);  
        printf("%d\n", ans);  
    }  
    return 0;  
}  

#include 

const int maxn = 5;
char map[maxn][maxn];
int ans, n;

bool isok(int x, int y) {
	for (int i = x + 1; i <= n && map[i][y] != 'X'; i++)
		if(map[i][y] == '0')
			return false;
	for (int i = x - 1; i >= 1 && map[i][y] != 'X'; i--)
		if(map[i][y] == '0')
			return false;
	for (int i = y; i <= n && map[x][i] != 'X'; i++)
		if (map[x][i] == '0')
			return false;
	for (int i = y - 1; i >= 1 && map[x][i] != 'X'; i--)
		if (map[x][i] == '0')
			return false;
	return true;
}

void dfs(int x, int y, int p) {
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (map[i][j] == '.' && isok(i, j)) {
				map[i][j] = '0';
				dfs(i, j, p + 1);
				map[i][j] = '.';
			}
	if (ans < p)
		ans = p;
}

int main() {
	while (scanf("%d", &n) && n) {
		gets(map[0]);
		for (int i = 1; i <= n; i++)
			gets(map[i] + 1);
		ans = 0;
		dfs(1, 1, 0);
		printf("%d\n", ans);
	}
	return 0;
}

冲突。

N皇后一行只能放一个，而这题不行，所以用全图暴力放棋，回溯dfs即可，题目最多就到4*4，范围很小。

刚开始考虑放一个棋子后就把其他不能放的地方标记下，然后再暴力，后来发现如果一个点重复标记在去标记时就会把点标成合法的，于是改用放棋子是进行检查，由于数据量小，也不会占用多少时间。

之后才想到，在标记时可以用累加的，去标记时再一个一个减下来即可。。。

代码：