uva 639 Dont Get Rooked 變形N皇後問題 暴力回溯

題目：跟N皇後問題一樣，不考慮對角沖突，但考慮牆的存在，只要中間有牆就不會

#include <cstdio>   
  
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 <cstdio>

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，范圍很小。

剛開始考慮放一個棋子後就把其他不能放的地方標記下，然後再暴力，後來發現如果一個點重復標記在去標記時就會把點標成合法的，於是改用放棋子是進行檢查，由於數據量小，也不會占用多少時間。

之後才想到，在標記時可以用累加的，去標記時再一個一個減下來即可。。。

代碼：