目录
*前置题目
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 9, M = 1 << N;
int mp[M], bit_cnt[M];
char g[N * N];
int row[N], col[N], cell[3][3];
// 初始化所有数字是可用的
void init() {
for (int i = 0; i < N; ++i) row[i] = col[i] = M - 1;
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
cell[i][j] = M - 1;
}
}
}
void draw(int x, int y, int c, bool tag) {
g[x * N + y] = tag ? c + '1' : '.';
int val = 1 << c;
if (!tag) val = -val;
row[x] -= val;
col[y] -= val;
cell[x / 3][y / 3] -= val;
}
int lowbit(int x) {
return x & -x;
}
int get(int x, int y) {
return row[x] & col[y] & cell[x / 3][y / 3];
}
bool dfs(int cnt) {
if (cnt == 0) return true;
int x, y, min_s;
int min_cnt = N;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (g[i * N + j] == '.') {
int s = get(i, j);
if (bit_cnt[s] < min_cnt) {
min_s = s;
min_cnt = bit_cnt[s];
x = i, y = j;
}
}
}
}
for (int i = min_s; i; i -= lowbit(i)) {
int val = mp[lowbit(i)];
draw(x, y, val, true);
if (dfs(cnt - 1)) return true;
draw(x, y, val, false);
}
return false;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
// 初始化每个二进制数对应的数字是多少
for (int i = 0; i < N; ++i) mp[1 << i] = i;
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
bit_cnt[i] += i >> j & 1;
}
}
while (cin >> g, g[0] != 'e') {
init();
int cnt = 0;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (g[i * N + j] != '.') {
int val = g[i * N + j] - '1';
draw(i, j, val, true);
}
else cnt++;
}
}
dfs(cnt);
for (int i = 0; i < N * N; ++i) cout << g[i];
cout << "\n";
}
return 0;
}
题目
算法标签: 搜索, d f s dfs dfs, 剪枝优化, D a c i n g − L i n k s Dacing-Links Dacing−Links
思路
位运算优化或者精确覆盖问题优化
*改了好久的 b u g bug bug代码(无法AC
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 9, M = 1 << N;
char g[N][N];
int row[N], col[N], cell[3][3];
int mp[M], bit_cnt[M];
int ans;
void init() {
for (int i = 0; i < N; ++i) row[i] = col[i] = M - 1;
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
cell[i][j] = M - 1;
}
}
}
void draw(int x, int y, int c, bool tag) {
int val = 1 << c;
g[x][y] = tag ? '1' + c : '0';
if (!tag) val = -val;
row[x] -= val;
col[y] -= val;
cell[x / 3][y / 3] -= val;
}
int get_score() {
const int score[N][N] = {
{
6, 6, 6, 6, 6, 6, 6, 6, 6},
{
6, 7, 7, 7, 7, 7, 7, 7, 6},
{
6, 7, 8, 8, 8, 8, 8, 7, 6},
{
6, 7, 8, 9, 9, 9, 8, 7, 6},
{
6, 7, 8, 9, 10, 9, 8, 7, 6},
{
6, 7, 8, 9, 9, 9, 8, 7, 6},
{
6, 7, 8, 8, 8, 8, 8, 7, 6},
{
6, 7, 7, 7, 7, 7, 7, 7, 6},
{
6, 6, 6, 6, 6, 6, 6, 6, 6}
};
int res = 0;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (g[i][j] != '0') {
res += (g[i][j] - '0') * score[i][j];
}
}
}
return res;
}
int get(int x, int y) {
return row[x] & col[y] & cell[x / 3][y / 3];
}
int lowbit(int x) {
return x & -x;
}
void dfs(int cnt) {
if (cnt == 0) {
ans = max(ans, get_score());
return;
}
int x = -1, y = -1, min_s;
int min_cnt = N;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (g[i][j] == '0') {
int s = get(i, j);
int cnt = bit_cnt[s];
if (cnt < min_cnt) {
min_cnt = cnt;
min_s = s;
x = i, y = j;
if (min_cnt == 1) break;
}
}
}
if (min_cnt == 1) break;
}
if (x == -1 || y == -1) return;
for (int i = min_s; i; i -= lowbit(i)) {
int c = mp[lowbit(i)];
draw(x, y, c, true);
dfs(cnt - 1);
draw(x, y, c, false);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
for (int i = 0; i < N; ++i) mp[1 << i] = i;
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
bit_cnt[i] += i >> j & 1;
}
}
init();
int cnt = 0;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
char c;
cin >> c;
if (c != '0') {
draw(i, j, c - '1', true);
} else cnt++;
}
}
dfs(cnt);
cout << ans << "\n";
return 0;
}
增量式优化计算代码
边计算边统计分数, 效率更高
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 9, M = 1 << N;
int g[N][N];
int row[N], col[N], cell[3][3];
int mp[M], bit_cnt[M];
int ans = -1;
int lowbit(int x) {
return x & -x;
}
void init() {
for (int i = 0; i < N; ++i) mp[1 << i] = i + 1;
for (int i = 0; i < M; ++i) {
bit_cnt[i] = 0;
for (int j = 0; j < N; ++j) {
bit_cnt[i] += i >> j & 1;
}
}
for (int i = 0; i < N; ++i) row[i] = col[i] = M - 1;
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
cell[i][j] = M - 1;
}
}
}
int get_score(int x, int y, int val) {
return (min(min(x, 8 - x), min(y, 8 - y)) + 6) * val;
}
void draw(int x, int y, int c, bool tag) {
g[x][y] = tag ? c : 0;
int val = 1 << (c - 1);
if (!tag) val = -val;
row[x] -= val;
col[y] -= val;
cell[x / 3][y / 3] -= val;
}
int get(int x, int y) {
return row[x] & col[y] & cell[x / 3][y / 3];
}
void dfs(int cnt, int score) {
if (cnt == 0) {
ans = max(ans, score);
return;
}
int min_cnt = N + 1;
int x, y;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (g[i][j] == 0) {
int s = get(i, j);
int cnt = bit_cnt[s];
if (cnt < min_cnt) {
min_cnt = cnt;
x = i, y = j;
}
}
}
}
int s = get(x, y);
for (int i = s; i; i -= lowbit(i)) {
int val = lowbit(i);
int c = mp[val];
draw(x, y, c, true);
dfs(cnt - 1, score + get_score(x, y, c));
draw(x, y, c, false);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
init();
int cnt = 0, score = 0;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
int c;
cin >> c;
if (c != 0) {
draw(i, j, c, true);
score += get_score(i, j, c);
}
else cnt++;
}
}
dfs(cnt, score);
cout << ans << "\n";
return 0;
}
京公网安备 11010502036488号