1 #include<cstdio>  2 #include<iostream>  3 #include<cstring>  4 #include<algorithm>  5 #include<cmath>  6 #include<iomanip>   7 using namespace std;  8   9 const int n=729,m=324; 10 bool mx[2000][2000];//数独转化过来的01矩阵  11 int map[10][10],cnt[2000],head,cur,ans; 12 int sqr[10][10]={{0,0,0,0,0,0,0,0,0,0},  //九宫格的编号  13                {0,1,1,1,4,4,4,7,7,7}, 14                {0,1,1,1,4,4,4,7,7,7}, 15                {0,1,1,1,4,4,4,7,7,7}, 16                {0,2,2,2,5,5,5,8,8,8}, 17                {0,2,2,2,5,5,5,8,8,8}, 18                {0,2,2,2,5,5,5,8,8,8}, 19                {0,3,3,3,6,6,6,9,9,9}, 20                {0,3,3,3,6,6,6,9,9,9}, 21                {0,3,3,3,6,6,6,9,9,9}}; 22  23 int w[10][10]={{0,0,0,0,0,0,0,0,0,0}, 24                {0,6,6,6,6,6,6,6,6,6}, 25                {0,6,7,7,7,7,7,7,7,6}, 26                {0,6,7,8,8,8,8,8,7,6}, 27                {0,6,7,8,9,9,9,8,7,6}, 28                {0,6,7,8,9,10,9,8,7,6}, 29                {0,6,7,8,9,9,9,8,7,6}, 30                {0,6,7,8,8,8,8,8,7,6}, 31                {0,6,7,7,7,7,7,7,7,6}, 32                {0,6,6,6,6,6,6,6,6,6}}; 33                 34 struct point 35 { 36     int row,lc,rc,up,down,col;//元素的上下左右，行号和列标  37 }node[2000*2000]; 38  39 inline int id(int x,int y) 40 { 41     return (x-1)*9+y;//格子（x，y）的编号  42 } 43  44 void init(int c)//初始化列标元素  45 { 46     for (int i=0;i<=c;i++) 47     { 48         node[i].lc=i-1; 49         node[i].rc=i+1; 50         node[i].up=node[i].down=node[i].col=i; 51     } 52     node[0].lc=c; 53     node[c].rc=0; 54 } 55  56 void build_link()//把01矩阵中的 1 用dancing link 连接  57 { 58     cur=m; 59     for (int i=1;i<=n;i++) 60     { 61         int start,pre; 62         start=pre=cur+1; 63         for (int j=1;j<=m;j++) 64             if (mx[i][j]) 65             { 66                 cur++; 67                 cnt[j]++; 68                 node[cur].row=i; 69                  70                 node[cur].lc=pre; 71                 node[cur].rc=start; 72                 node[pre].rc=cur; 73                 node[start].lc=cur; 74                  75                 node[cur].col=j; 76                 node[cur].up=node[j].up; 77                 node[cur].down=j; 78                 node[node[j].up].down=cur; 79                 node[j].up=cur; 80                 pre=cur; 81             } 82     } 83 } 84  85 inline void cover(int c)//删除冲突元素  86 { 87     for (int i=node[c].up;i!=c;i=node[i].up) 88         for (int j=node[i].rc;j!=i;j=node[j].rc) 89         { 90             node[node[j].up].down=node[j].down; 91             node[node[j].down].up=node[j].up; 92             cnt[node[j].col]--; 93         } 94     node[node[c].lc].rc=node[c].rc; 95     node[node[c].rc].lc=node[c].lc; 96 } 97  98 inline void uncover(int c)//恢复冲突元素  99 {100     for (int i=node[c].up;i!=c;i=node[i].up)101         for (int j=node[i].rc;j!=i;j=node[j].rc)102         {103             node[node[j].up].down=j;104             node[node[j].down].up=j;105             cnt[node[j].col]++;106         }107     node[node[c].lc].rc=c;108     node[node[c].rc].lc=c;109 }110 111 void read_data()//把数独转化成01矩阵 112 {113     for (int i=1;i<=9;i++)114         for (int j=1;j<=9;j++)115         {116             scanf("%d",&map[i][j]);117             int c=id(i,j),t,k;118             if (map[i][j])//数独中本来有数，直接加入 119             {120                 k=map[i][j];121                 t=(c-1)*9+k;122                 mx[t][c]=true;123                 mx[t][81+9*(i-1)+k]=true;124                 mx[t][162+9*(j-1)+k]=true;125                 mx[t][243+(sqr[i][j]-1)*9+k]=true;126             }127             else 128             {129                 for (k=1;k<=9;k++) //数独中本来没数，那么加入1-9的情况 130                 {131                     t=(c-1)*9+k;132                     mx[t][c]=true;133                     mx[t][81+9*(i-1)+k]=true;134                     mx[t][162+9*(j-1)+k]=true;135                     mx[t][243+(sqr[i][j]-1)*9+k]=true;136                 }137             }138         }139 }140 141 bool dfs(int step,int score)142 {143     if (node[head].rc==head) //已经全部覆盖 144     {145         ans=max(score,ans);146         return true;147     }148     149     int i,j,c,t=210000,x,y,num,flag=0;150     for (i=node[head].rc;i!=head;i=node[i].rc) //启发式，每次处理元素最少的列 151         if (cnt[i]<t)152         {153             t=cnt[i];154             c=i;155         }156     if (t==0)157         return false;158         159     cover(c);//覆盖当前列 160     161     for (i=node[c].down;i!=c;i=node[i].down)162     {163         for (j=node[i].lc;j!=i;j=node[j].lc)//删除冲突的行 164             cover(node[j].col);165         num=(node[i].row-1)/9+1;166         x=(num-1)/9+1;167         y=num-9*(x-1);168         flag|=dfs(step+1,score+w[x][y]*(node[i].row-(num-1)*9));169         for (j=node[i].rc;j!=i;j=node[j].rc)//恢复删除冲突的行 170             uncover(node[j].col);171     }172     173     uncover(c);//恢复当前列 174     return flag;175 }176 177 void solve()178 {179     init(m);180     build_link();181     int flag=1;182     if (!dfs(1,0))183         printf("-1\n");184     else printf("%d\n",ans);185 }186 187 int main()188 {189     read_data();190     solve();191     return 0;192 }