知识点:深搜,剪枝,位运算
难度:5
这个题是做完李煜东蓝书例题之后来做的,简直是一模一样,也就是个填数独,无非就是加了一个中间记录更新答案,这个题洛谷的数据,用李煜东深搜那一节讲的数独题,也就是3074就能过,主要的优化就是优化搜索顺序和状压,至于剪枝那一节的数独题,是个黑题,作为初学者,还是等做的题多了,知识储备多了,再去想那个题,虽然那个题也用不到什么知识,也还是剪枝
主要是两个优化,第一是优化搜索顺序,指的是我们每次搜索都找备用选项最少的未填空格填数,所以我们每次深搜开始都要遍历,去找备用选项最少的空格,第二是这整个题都是用位运算来实现的,我们开三个数组,分别是记录行列块里面可以使用的选项,我们要做的预处理有,二进制数对应的备用选项的映射,每个数里面都有多少个1,然后就是三个状压数组的初始化,然后根据输入修改一下,这里一个小细节需要注意,就是我们二进制数第0为映射的是1,以此类推,然后每个方格的权值也要初始化一下,这里用的方法还是感觉比较简便的,然后就是深搜,主要分为两大块,第一个就是找备用选项数目最小的格子,这个就是剪枝里面的优化搜索顺序,为什么要这样呢,感性的感觉一下也能想到这样是对的,分支的数目是这种搜索题超时最主要的原因,因为分支是要乘的,这样做就是减少每个状态向下继续搜索的分支,然后第二个部分就是我们开始给上面找到的格子填数,回溯深搜,就行了
- #include
-
- using namespace std;
-
- const int N = 9;
-
- int a[N][N], b[N][N], h1[1 << N], h2[1 << N];
- int row[N], col[N], block[3][3], ans, flag;
-
- inline int lowbit(int x) {
- return x & -x;
- }
-
- inline int get(int x, int y) {
- return row[x] & col[y] & block[x / 3][y / 3];
- }
-
- void dfs(int k, int cur) {
- if (!k) {
- flag = 1;
- if (ans < cur) ans = cur;
- return;
- }
- int x, y, Min = 10;
- for (int i = 0; i < 9; i++) {
- for (int j = 0; j < 9; j++) {
- if (!a[i][j] && h2[get(i, j)] < Min) {
- Min = h2[get(i, j)];
- x = i; y = j;
- }
- }
- }
- for (int i = get(x, y); i; i -= lowbit(i)) {
- int t = lowbit(i);
- row[x] -= t;
- col[y] -= t;
- block[x / 3][y / 3] -= t;
- a[x][y] = h1[t] + 1;
- dfs(k - 1, cur + b[x][y] * a[x][y]);
- row[x] += t;
- col[y] += t;
- block[x / 3][y / 3] += t;
- a[x][y] = 0;
- }
- }
-
- int main() {
- for (int i = 0; i < 9; i++) h1[1 << i] = i;
- for (int i = 0; i < (1 << 9); i++) {
- int cnt = 0;
- for (int j = i; j; j -= lowbit(j)) cnt++;
- h2[i] = cnt;
- }
- for (int i = 0; i < 9; i++) {
- row[i] = col[i] = (1 << 9) - 1;
- }
- for (int i = 0; i < 3; i++) {
- for (int j = 0; j < 3; j++) {
- block[i][j] = (1 << 9) - 1;
- }
- }
- for (int i = 0; i < 9; i++) {
- for (int j = 0; j < 9; j++) {
- b[i][j] = 10 - max(abs(i - 4), abs(j - 4));
- }
- }
- int cnt = 0;
- for (int i = 0; i < 9; i++) {
- for (int j = 0; j < 9; j++) {
- cin >> a[i][j];
- if (a[i][j]) {
- int t = a[i][j] - 1;
- row[i] -= 1 << t;
- col[j] -= 1 << t;
- block[i / 3][j / 3] -= 1 << t;
- ans += b[i][j] * a[i][j];
- } else cnt++;
- }
- }
- dfs(cnt, ans);
- cout << (flag ? ans : -1);
- return 0;
- }