2082: 靶形數獨
Time Limit: 2000 ms ?? Memory Limit: 131072 kB??
Judge type: Multi-cases (Detailed Mode - 20 cases)
Total Submit : 181?(41 users)???Accepted Submit : 25?(15 users)???Page View : 1792? Font Style: Aa Aa Aa 小城和小華都是熱愛數學的好學生，最近，他們不約而同地迷上了數獨游戲，好勝的他們想用數獨來一比高低。但普通的數獨對他們來說都過于簡單了，于是他們向 Z博士請教，Z 博士拿出了他最近發明的“靶形數獨” ，作為這兩個孩子比試的題目。
???? 靶形數獨的方格同普通數獨一樣，在 9 格寬×9 格高的大九宮格中有 9 個 3 格寬×3 格高的小九宮格（用粗黑色線隔開的） 。在這個大九宮格中，有一些數字是已知的，根據這些數字，利用邏輯推理，在其他的空格上填入 1到 9 的數字。每個數字在每個小九宮格內不能重復出現，每個數字在每行、每列也不能重復出現。但靶形數獨有一點和普通數獨不同，即每一個方格都有一個分值，而且如同一個靶子一樣，離中心越近則分值越高。 （如圖）
上圖具體的分值分布是：最里面一格（黃色區域）為 10 分，黃色區域外面的一圈（紅色區域）每個格子為 9 分，再外面一圈（藍色區域）每個格子為 8分，藍色區域外面一圈（棕色區域）每個格子為 7分，最外面一圈（白色區域）每個格子為 6 分，如上圖所示。
???? 比賽的要求是：每個人必須完成一個給定的數獨（每個給定數獨可能有不同的填法） ，而且要爭取更高的總分數。而這個總分數即每個方格上的分值和完成這個數獨時填在相應格上的數字的乘積的總和。如圖，在以下的這個已經填完數字的靶形數獨游戲中，總分數為 2829。游戲規定，將以總分數的高低決出勝負。
?
???? 由于求勝心切，小城找到了善于編程的你，讓你幫他求出，對于給定的靶形數獨，能夠得到的最高分數。

Input

一共 9 行。每行 9 個整數（每個數都在 0—9 的范圍內） ，表示一個尚未填滿的數獨方格，未填的空格用“0”表示。每兩個數字之間用一個空格隔開。

Output

輸出可以得到的靶形數獨的最高分數。如果這個數獨無解，則輸出整數-1。

Sample Input

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

Sample Output

2829

Hint

40%的數據，數獨中非 0數的個數不少于 30。
80%的數據，數獨中非 0數的個數不少于 26。
100%的數據，數獨中非 0 數的個數不少于 24。

Source

NOIP 2009 提高組

Best User : nehzilrz

?

?

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
#define N 1005
#define V 1020005
int U[V],D[V];
int L[V],R[V];
int C[V];
int H[N],S[N];
int mark[V];
int size,n,m,OK[N],flag;
int tnum[V];
void Link(int r,int c)
{
??? S[c]++;C[size]=c;
??? U[size]=U[c];D[U[c]]=size;
??? D[size]=c;U[c]=size;
??? if(H[r]==-1) H[r]=L[size]=R[size]=size;
??? else
??? {
??????? L[size]=L[H[r]];R[L[H[r]]]=size;
??????? R[size]=H[r];L[H[r]]=size;
??? }
??? mark[size]=r;
??? size++;
}
void remove(int c)//刪除列
{
??? int i,j;
??? L[R[c]]=L[c];
??? R[L[c]]=R[c];
??? for(i=D[c];i!=c;i=D[i])
??? {
??????? for(j=R[i];j!=i;j=R[j])
??????? {
??????????? U[D[j]]=U[j],D[U[j]]=D[j];
??????????? S[C[j]]--;
??????? }
??? }
}
void resume(int c)
{
??? int i,j;
??? for(i=U[c];i!=c;i=U[i])
??? {
??????? for(j=L[i];j!=i;j=L[j])
??????? {
??????????? U[D[j]]=j;D[U[j]]=j;
??????????? S[C[j]]++;
??????? }
??? }
??? L[R[c]]=c;
??? R[L[c]]=c;
}
int ans;
int fen[100],x[N],y[N];//輸出所有解用的
void Dance(int k)
{
??? int i,j,Min,c;
??? if(!R[0])
??? {
??????? flag=1;//標記有解
??????? //sort(OK, OK+k);
??????? int cnt=0;
??????? for(int i=0;i<k;i++)
??????? {
??????????? int t=mark[OK[i]];
??????????? int pos=x[t]*9+y[t];
??????????? cnt+=fen[pos]*tnum[t];
??????? }
??????? ans=max(ans,cnt);
??????? return;
??? }
??? for(Min=N,i=R[0];i;i=R[i])
??????? if(S[i]<Min) Min=S[i],c=i;
??? remove(c);//刪除該列
??? for(i=D[c];i!=c;i=D[i])
??? {
??????? OK[k]=i;
??????? for(j=R[i];j!=i;j=R[j])
??????????? remove(C[j]);
??????? Dance(k+1);
??????? //if(flag) return;//只要一組解
??????? for(j=L[i];j!=i;j=L[j])
??????????? resume(C[j]);
??? }
??? resume(c);
}
/*
試構造一個矩陣，其中以行表示概然，以列表示約束。
行所表示的概然狀態為（r,c,k）即在棋盤r行c列放置數字k。
列所表示的約束分做四種，即改當前方案r行中是否放置數k，c列中是否放置數k，
(r,c)格中是否放置數k以及塊b(即所屬區域)是否放置數k。
因此行總共有N*N*N=9*9*9=729個，列總共有9*9*4=324個，要求取若干數字擺放的方案(行)，
使每個數字在棋盤的行、列、區域塊中(列)只出現一次(1個‘1’)，問題轉化為729*324的
矩陣的精確覆蓋。特別的，(r,c)格的約束保證了我們最后可行解的一定為N*N。
*/
char str[100];
int mat[N][N];
int a[10][10];
int tof(int x,int y)
{
??? return x*9+y;
}
int main()
{
??? for(int i=0;i<5;i++)
??? {
??????? for(int j=i;j<9-i;j++)
??????????? fen[tof(i,j)]=i+6,fen[tof(9-i-1,j)]=i+6,
??????????? fen[tof(j,i)]=i+6,fen[tof(j,9-i-1)]=i+6;
??? }
??? //for(int i=0;i<9;i++){for(int j=0;j<9;j++) printf("%-3d",fen[tof(i,j)]);printf("\n");}
??? while(scanf("%d",&a[0][0])==1)
??? {
??????? for(int i=0;i<9;i++) for(int j=0;j<9;j++)
??????????? if(i||j) scanf("%d",&a[i][j]);
??????? //DLX
??????? m=9*9*4;//列數
??????? n=0;//構圖花費時間比較多? 應該直接構圖 不用mat數組? 這樣會快很多
??????? for(int i=0;i<=m;i++)
??????? {
??????????? S[i]=0;
??????????? D[i]=U[i]=i;
??????????? L[i+1]=i;R[i]=i+1;
??????? }R[m]=0;
??????? size=m+1;
??????? memset(H,-1,sizeof(H));
??????? memset(mark,0,sizeof(mark));//不用mat數組,這樣可以加快速度
??????? for(int i=1;i<=9;i++)
??????? {
??????????? for(int j=1;j<=9;j++)
??????????? {
??????????????? int row=i;
??????????????? int col=j;
??????????????? int kuai=(i-1)/3*3+(j-1)/3+1;
??????????????? int pos=(i-1)*9+j;
??????????????? if(a[i-1][j-1]==0)//可以放數字
??????????????? {
??????????????????? for(int k=1;k<=9;k++)
??????????????????? {
??????????????????????? ++n;
??????????????????????? tnum[n]=k;x[n]=i-1,y[n]=j-1;
??????????????????????? Link(n,(row-1)*9+k);//行
??????????????????????? Link(n,81+(col-1)*9+k);//列
??????????????????????? Link(n,162+(kuai-1)*9+k);//塊
??????????????????????? Link(n,243+pos);//位置
??????????????????? }
??????????????? }
??????????????? else//已經放數字
??????????????? {
??????????????????? int k=a[i-1][j-1];
??????????????????? ++n;
??????????????????? tnum[n]=k;x[n]=i-1,y[n]=j-1;
??????????????????? Link(n,(row-1)*9+k);//行
??????????????????? Link(n,81+(col-1)*9+k);//列
??????????????????? Link(n,162+(kuai-1)*9+k);//塊
??????????????????? Link(n,243+pos);//位置
??????????????? }
??????????? }
??????? }
??????? flag=0,ans=0;
??????? Dance(0);
??????? if(flag) printf("%d\n",ans);
??????? else printf("-1\n");
??? }
??? return 0;
}
/*
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

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

2829?? 2852
*/

?

總結

以上是生活随笔為你收集整理的nankai 2082: 靶形数独 数独(9*9)求所有解 DLX+精确覆盖的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。