題目描述 小城和小華都是熱愛數學的好學生，最近，他們不約而同地迷上了數獨游戲，好勝的他 們想用數獨來一比高低。但普通的數獨對他們來說都過於簡單了，於是他們向 Z 博士請教， Z 博士拿出了他最近發明的“靶形數獨”，作為這兩個孩子比試的題目。 靶形數獨的方格同普通數獨一樣，在 9 格寬×9 格高的大九 ...
題目描述
小城和小華都是熱愛數學的好學生，最近，他們不約而同地迷上了數獨游戲，好勝的他
們想用數獨來一比高低。但普通的數獨對他們來說都過於簡單了，於是他們向 Z 博士請教，
Z 博士拿出了他最近發明的“靶形數獨”，作為這兩個孩子比試的題目。
靶形數獨的方格同普通數獨一樣，在 9 格寬×9 格高的大九宮格中有 9 個 3 格寬×3 格
高的小九宮格（用粗黑色線隔開的）。在這個大九宮格中，有一些數字是已知的，根據這些數字，利用邏輯推理，在其他的空格上填入 1 到 9 的數字。每個數字在每個小九宮格內不能
重覆出現，每個數字在每行、每列也不能重覆出現。但靶形數獨有一點和普通數獨不同，即
每一個方格都有一個分值，而且如同一個靶子一樣，離中心越近則分值越高。（如圖）
上圖具體的分值分佈是：最裡面一格（黃色區域）為 10 分，黃色區域外面的一圈（紅
色區域）每個格子為 9 分，再外面一圈（藍色區域）每個格子為 8 分，藍色區域外面一圈（棕
色區域）每個格子為 7 分，最外面一圈（白色區域）每個格子為 6 分，如上圖所示。比賽的
要求是：每個人必須完成一個給定的數獨（每個給定數獨可能有不同的填法），而且要爭取
更高的總分數。而這個總分數即每個方格上的分值和完成這個數獨時填在相應格上的數字
的乘積的總和
總分數即每個方格上的分值和完成這個數獨時填在相應格上的數字
的乘積的總和。如圖，在以下的這個已經填完數字的靶形數獨游戲中，總分數為 2829。游戲規定，將以總分數的高低決出勝負。
由於求勝心切，小城找到了善於編程的你，讓你幫他求出，對於給定的靶形數獨，能
夠得到的最高分數。
輸入輸出格式
輸入格式：
一共 9 行。每行 9 個整數（每個數都在 0―9 的範圍內），表示一個尚未填滿的數獨方
格，未填的空格用“0”表示。每兩個數字之間用一個空格隔開。
輸出格式：
輸出文件 sudoku.out 共 1 行。
輸出可以得到的靶形數獨的最高分數。如果這個數獨無解，則輸出整數-1。
輸入輸出樣例
輸入樣例#1：sudoku1 7 0 0 9 0 0 0 0 1 1 0 0 0 0 5 9 0 0 0 0 0 2 0 0 0 8 0 0 0 5 0 2 0 0 0 3 0 0 0 0 0 0 6 4 8 4 1 3 0 0 0 0 0 0 0 0 7 0 0 2 0 9 0 2 0 1 0 6 0 8 0 4 0 8 0 5 0 4 0 1 2 sudoku2 0 0 0 7 0 2 4 5 3 9 0 0 0 0 8 0 0 0 7 4 0 0 0 5 0 1 0 1 9 5 0 8 0 0 0 0 0 7 0 0 0 0 0 2 5 0 3 0 5 7 9 1 0 8 0 0 0 6 0 1 0 0 0 0 6 0 9 0 0 0 0 1 0 0 0 0 0 0 0 0 6輸出樣例#1：
sudoku1 2829 sudoku2 2852
說明
【數據範圍】
40%的數據，數獨中非 0 數的個數不少於 30。
80%的數據，數獨中非 0 數的個數不少於 26。
100%的數據，數獨中非 0 數的個數不少於 24。
NOIP 2009 提高組 第四題
- 看完題目，貌似沒有什麼更好的解決方法，那就搜索了。
- 但是通過觀察數據範圍，如果沒有什麼好的搜索策略，複雜度大概為O（sum^9），這不是個理想的策略。
- 簡單易想的剪枝策略：一邊搜一邊判斷，大概能優化很多，期望得分60分。
- 通過題意可以得出一個較好的搜索策略：根據每行每列需要搜索的數字個數（即開始數獨前未給出數字的格子的個數）統計出來，根據個數從小到大排序，得出一個較好的行列搜索順序。
- 然後就搜吧！
- 期望得分100分。
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 5 struct ha{ 6 int m,cnt; 7 } a[15]; 8 9 struct li{ 10 int m,cnt; 11 } b[15]; 12 13 bool cmp1(const ha x,const ha y) { 14 return (x.cnt>y.cnt); 15 } 16 17 bool cmp2(const li x,const li y) { 18 return x.cnt>y.cnt; 19 } 20 21 const int w[10][10]= 22 {0,0,0,0,0,0,0,0,0,0, 23 0,6,6,6,6,6,6,6,6,6, 24 0,6,7,7,7,7,7,7,7,6, 25 0,6,7,8,8,8,8,8,7,6, 26 0,6,7,8,9,9,9,8,7,6, 27 0,6,7,8,9,10,9,8,7,6, 28 0,6,7,8,9,9,9,8,7,6, 29 0,6,7,8,8,8,8,8,7,6, 30 0,6,7,7,7,7,7,7,7,6, 31 0,6,6,6,6,6,6,6,6,6}; 32 33 const int num[10][10]= 34 {0,0,0,0,0,0,0,0,0,0, 35 0,1,1,1,2,2,2,3,3,3, 36 0,1,1,1,2,2,2,3,3,3, 37 0,1,1,1,2,2,2,3,3,3, 38 0,4,4,4,5,5,5,6,6,6, 39 0,4,4,4,5,5,5,6,6,6, 40 0,4,4,4,5,5,5,6,6,6, 41 0,7,7,7,8,8,8,9,9,9, 42 0,7,7,7,8,8,8,9,9,9, 43 0,7,7,7,8,8,8,9,9,9}; 44 45 int n=9,x,tot,kashi,ans=-1,sum=0,map[15][15],quex[15],quey[15]; 46 bool f[15][15],hang[15][15],lie[15][15],ge[15][15],wujie,ka; 47 48 void dfs(int u,int v) { 49 if (u>n) { 50 ans=max(ans,sum); 51 return; 52 } 53 int x=a[u].m; 54 int y=b[v].m; 55 if (f[x][y]) { 56 if (v<n) dfs(u,v+1); else dfs(u+1,1); 57 return; 58 } 59 for (int i=1; i<=9; i++) { 60 if (hang[x][i]) continue; 61 if (lie[y][i]) continue; 62 if (ge[num[x][y]][i]) continue; 63 hang[x][i]=1; 64 lie[y][i]=1; 65 ge[num[x][y]][i]=1; 66 sum+=w[x][y]*i; 67 if (v<n) dfs(u,v+1); else dfs(u+1,1); 68 hang[x][i]=0; 69 lie[y][i]=0; 70 ge[num[x][y]][i]=0; 71 sum-=w[x][y]*i; 72 } 73 } 74 75 int main() { 76 for (int i=1; i<=n; i++) { 77 for (int j=1; j<=n; j++) { 78 scanf("%d",&x); 79 if (x) { 80 a[i].cnt++; 81 b[j].cnt++; 82 hang[i][x]=1; 83 lie[j][x]=1; 84 ge[num[i][j]][x]=1; 85 sum+=w[i][j]*x; 86 f[i][j]=1; 87 } 88 } 89 } 90 for (int i=1; i<=n; i++) { 91 a[i].m=i; 92 b[i].m=i; 93 } 94 sort(a+1,a+n+1,cmp1); 95 sort(b+1,b+n+1,cmp2); 96 //for (int i=1; i<=n; i++) printf("%d ",a[i].m); 97 //for (int i=1; i<=n; i++) printf("%d ",b[i].m); 98 dfs(1,1); 99 printf("%d",ans); 100 return 0; 101 }
