HDU2553 N皇后(回溯)

题目链接

N皇后问题

题解:首先应该意识到,在棋盘(二维数组)中,同一条主对角线(左上到右下)上的点的y-x值相等,同一条副对角线(右上到左下)上的点的x+y值相等。用二维数组vis判断当前尝试的皇后所在列和两个对角线是否已存在其他皇后。主对角线y-x可能为负,加n即可。

void search(int cur){  //当前行
    if(cur == n){
        ans++;
        return;
    }
    for(int i = 0; i < n; i++){
        if(!vis[0][i] && !vis[1][cur+i] && !vis[2][cur-i+n]){ //分别代表列、副对角线、主对角线
            //C[cur] = i;       若不需打印解 可忽略C数组
            vis[0][i] = vis[1][cur+i] = vis[2][cur-i+n] = 1;
            search(cur+1);
            vis[0][i] = vis[1][cur+i] = vis[2][cur-i+n] = 0;
        }
    }
}

HDU这题直接交会超时,可能有重复数据,因为只有10个数,把答案打表一下就行了。

#include <iostream>
using namespace std;
int n=1,x[11]={0,1,0,0,2,10,4,40,92,352,724};
int main(){
    while(n!=0){
        cin >> n;
        if(n!=0) cout << x[n] << endl;
    }
    return 0;
}
Zhao Li /
Published under (CC) BY-NC-SA in categories 算法  tagged with DFS  八皇后  回溯