洛谷P1074 靶形数独【dfs】【剪枝】

题目：https://www.luogu.org/problemnew/show/P1074

题意：

数独的分数如下。一个数独的总分数就是权值乘所填数字之和。

现在给一个未完成的数独，问分数最高的数独的总分。

思路：

感觉dfs就是要学会各种剪枝。要敢于剪枝。

最基本的思路就是记下要填的位置和每行每列每个方块填数的情况，然后每个空格都1~9试过来。填完了计算分数。

但是如果仅仅是这样的话还是不行，只有75分TLE。

我们做数独的时候一般都是找零最少的某行某列或某个方格开始填，因为这样的可能性比较少。

这道题也应该考虑到这样的剪枝，不过只需要考虑行就行了，从空格最少的行开始搜索。

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 #include<map>
  4 #include<set>
  5 #include<iostream>
  6 #include<cstring>
  7 #include<algorithm>
  8 #include<vector>
  9 #include<cmath> 
 10 #include<queue>
 11 
 12 #define inf 0x7f7f7f7f
 13 using namespace std;
 14 typedef long long LL;
 15 typedef pair<int, int> pr;
 16 
 17 int mat[10][10];
 18 bool visrow[10][10];
 19 bool viscol[10][10];
 20 bool vissqu[10][10];
 21 
 22 int ans = -1;
 23 vector<pr>zeros;
 24 int n = 0;
 25 
 26 int getscore()
 27 {
 28     int tmp = 0;
 29     for(int i = 0; i < 9; i++){
 30         for(int j = 0; j < 9; j++){
 31             tmp += mat[i][j] * 6;
 32         }
 33     }
 34     for(int k = 1; k < 5; k++){
 35         for(int i = 0 + k; i < 9 - k; i++){
 36             for(int j = 0 + k; j < 9 - k; j++){
 37                 tmp += mat[i][j];
 38             }
 39         }
 40     }
 41     
 42     return tmp;
 43 }
 44 
 45 void dfs(int id)
 46 {
 47     if(id == n){
 48 //        for(int i = 0; i < 9; i++){
 49 //            for(int j = 0; j < 9; j++){
 50 //                printf("%d ", mat[i][j]);
 51 //            }
 52 //            printf("
");
 53 //        }
 54 //        printf("%d

", getscore());
 55         
 56         ans = max(ans, getscore());
 57     }
 58     int i = zeros[id].first;
 59     int j = zeros[id].second;
 60     for(int k = 1; k <= 9; k++){
 61         if(!visrow[i][k] && !viscol[j][k] && !vissqu[i / 3 * 3+ j / 3][k]){
 62             mat[i][j] = k;
 63             visrow[i][k] = viscol[j][k] = vissqu[i / 3 * 3+ j / 3][k] = true;
 64             dfs(id + 1);
 65             visrow[i][k] = viscol[j][k] = vissqu[i / 3 * 3+ j / 3][k] = false;
 66             mat[i][j] = 0;
 67         }
 68     }
 69     return;
 70 }
 71 
 72 vector<int>zero[10];
 73 struct node{
 74     int row, cnt;
 75 }rows[10];
 76 
 77 bool cmp(node a, node b)
 78 {
 79     return a.cnt < b.cnt;
 80 }
 81 
 82 int main()
 83 {
 84     for(int i = 0; i < 9; i++){
 85         rows[i].row = i;
 86         for(int j = 0; j < 9; j++){
 87             scanf("%d", &mat[i][j]);
 88             if(mat[i][j]){
 89                 visrow[i][mat[i][j]] = true;
 90                 viscol[j][mat[i][j]] = true;
 91                 vissqu[i / 3 * 3+ j / 3][mat[i][j]] = true;
 92             }
 93             else{
 94                 rows[i].cnt++;
 95                 zero[i].push_back(j);
 96                 n++;
 97             }
 98         }
 99     }
100     sort(rows, rows + 9, cmp);
101     for(int i = 0; i < 9; i++){
102         int r = rows[i].row;
103         for(int j = 0; j < rows[i].cnt; j++){
104             zeros.push_back(make_pair(r, zero[r][j]));
105         }
106     }
107     
108     dfs(0);
109     printf("%d
", ans);
110     
111     return 0;
112 }