2
HDU2553 N皇后（回溯）
source link: https://arminli.com/hdu2553/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Armin's Blog
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;
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK