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 "); 184 else printf("%d ",ans); 185 } 186 187 int main() 188 { 189 read_data(); 190 solve(); 191 return 0; 192 }