HDU2553 N皇后(回溯)

December 22, 2015

题目链接

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;
}

Profile picture

Written by Armin Li , a venture capitalist. [Weibo] [Subscribe]