洛谷 1219:八皇后 (位运算 & DFS)

时间:2021-10-15 16:40:40

题目链接: https://www.luogu.org/problem/show?pid=1219#sub

row:受上面的皇后通过列控制的位置

ld:受上面的皇后通过从右至左的斜对角线控制的位置

rd:受上面的皇后通过从左至右的斜对角线控制的位置

upperlim:每一列都被控制时row的状况

 #include <cstdio>
using namespace std;
int upperlim, c, cnt, sum, ans[][], a[], n;
void test(int row, int ld, int rd) {
if (row == upperlim) {
if (cnt < ) {
for (int j = ; j < n; j++)
ans[cnt][j] = a[j]; //找到一个解,记录路径
cnt++;
} sum++;
return ;
}
int pos = upperlim & ~(row | ld | rd); // 当前行的状况
while (pos) {
int bit = pos & (-pos); //取右边第一个1(详见树状数组)
int p = bit, m = ;
while (p) { p >>= ; m++;} //取其位置
pos -= bit; //搜索下一个位置
a[c++] = m; //记录路径
test(row | bit, (ld | bit) << , (rd | bit) >> );
a[--c] = ; //遍历完毕,删除该点
}
}
int main() {
scanf("%d", &n);
upperlim = ( << n) - ;
test(, , );
//printf("%d", cnt);
for (int i = ;i < cnt; i++){
for (int j = ; j < n; j++)
printf("%d ", ans[i][j]);
puts("");
}
printf("%d", sum);
return ;
}