AcWing 843. n-皇后问题 C++ 二进制优化
原题链接
中等
作者:
张立斌
,
2019-10-27 16:48:07
,
所有人可见
,
阅读 1205
BitCount类
class BitCount {
public:
explicit BitCount() : bitCountVec(0x100) {
for (uint32_t i = 0; i < bitCountVec.size(); ++i) {
bitCountVec[i] = bitCount1(i);
}
}
int operator()(int value) const { return (*this)(static_cast<uint32_t>(value)); }
int operator()(uint32_t value) const {
return bitCountVec[value >> 24] + bitCountVec[(value >> 16) & 0x0ff] +
bitCountVec[(value >> 8) & 0x0ff] + bitCountVec[value & 0x0ff];
}
private:
int bitCount1(uint32_t value) {
int cnt = 0;
while (value) {
++cnt;
value &= value - 1;
}
return cnt;
}
vector<int> bitCountVec;
};
BitCount bitCount;
Queen类
class Queen {
public:
void queen(int size) {
this->size = size;
queenVec.resize(size, string(size, '.'));
queenDfs(0, 0, 0, 0);
queenVec.clear();
}
private:
void queenDfs(int row, int col, int left, int right) {
if (row == size) {
for (const string &str : queenVec) {
puts(str.c_str());
}
puts("");
return;
}
int bits = (~(col | left | right)) & ((1 << size) - 1);
while (bits) {
const int bit = bits & (-bits);
const int colIndex = bitCount(bit - 1);
queenVec[row][colIndex] = 'Q';
queenDfs(row + 1, col | bit, (left | bit) << 1, (right | bit) >> 1);
queenVec[row][colIndex] = '.';
bits -= bit;
}
}
int size;
vector<string> queenVec;
};
main函数
#include <iostream>
#include <vector>
using namespace std;
int main(void) {
int n;
scanf("%d", &n);
Queen().queen(n);
return 0;
}