NOIP2009 提高组 靶形数独 题解

靶形数独题解

小城和小华都是热爱数学的好学生，最近，他们不约而同地迷上了数独游戏，好胜的他们想用数独来一比高低。但普通的数独对他们来说都过于简单了，于是他们向Z 博士请教，Z 博士拿出了他最近发明的“靶形数独”，作为这两个孩子比试的题目。靶形数独的方格同普通数独一样，在 9 格宽×9 格高的大九宫格中有9 个3 格宽×3 格高的小九宫格（用粗黑色线隔开的）。在这个大九宫格中，有一些数字是已知的，根据这些数字，利用逻辑推理，在其他的空格上填入1 到9 的数字。每个数字在每个小九宫格内不能重复出现，每个数字在每行、每列也不能重复出现。但靶形数独有一点和普通数独不同，即每一个方格都有一个分值，而且如同一个靶子一样，离中心越近则分值越高。

上图具体的分值分布是：最里面一格（黄色区域）为 10 分，黄色区域外面的一圈（红色区域）每个格子为9 分，再外面一圈（蓝色区域）每个格子为8 分，蓝色区域外面一圈（棕色区域）每个格子为7 分，最外面一圈（白色区域）每个格子为6 分，如上图所示。比赛的要求是：每个人必须完成一个给定的数独（每个给定数独可能有不同的填法），而且要争取更高的总分数。而这个总分数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和。如图，在以下的这个已经填完数字的靶形数独游戏中，总分数为2829。游戏规定，将以总分数的高低决出胜负。由于求胜心切，小城找到了善于编程的你，让你帮他求出，对于给定的靶形数独，能够得到的最高分数。

输入描述 Input Description

一共 9 行。每行9 个整数（每个数都在0―9 的范围内），表示一个尚未填满的数独方
格，未填的空格用“0”表示。每两个数字之间用一个空格隔开。< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPC9ibG9ja3F1b3RlPgoKPGgyPgrK5LP2w+jK9iA8c21hbGw+T3V0cHV0IERlc2NyaXB0aW9uPC9zbWFsbD48L2gyPgoKPGJsb2NrcXVvdGU+CjxwPgrK5LP2v8nS1LXDtb21xLDQ0M7K/bbAtcTX7rjft9bK/aGjyOe5+9XiuPbK/bbAzt694qOs1PLK5LP21fvK/S0xoaM8L3A+CjwvYmxvY2txdW90ZT4KCjxoMj4K0fnA/crkyOsgPHNtYWxsPlNhbXBsZSBJbnB1dDwvc21hbGw+PC9oMj4KCjxibG9ja3F1b3RlPgo8cD4Kob7K5MjryuSz9tH5wP0gMaG/PC9wPgo8cD4KNyAwIDAgOSAwIDAgMCAwIDE8YnI+CjEgMCAwIDAgMCA1IDkgMCAwPGJyPgowIDAgMCAyIDAgMCAwIDggMDxicj4KMCAwIDUgMCAyIDAgMCAwIDM8YnI+CjAgMCAwIDAgMCAwIDYgNCA4PGJyPgo0IDEgMyAwIDAgMCAwIDAgMDxicj4KMCAwIDcgMCAwIDIgMCA5IDA8YnI+CjIgMCAxIDAgNiAwIDggMCA0PGJyPgowIDggMCA1IDAgNCAwIDEgMjwvcD4KPHA+CqG+yuTI68rks/bR+cD9IDKhvzwvcD4KPHA+CjAgMCAwIDcgMCAyIDQgNSAzPGJyPgo5IDAgMCAwIDAgOCAwIDAgMDxicj4KNyA0IDAgMCAwIDUgMCAxIDA8YnI+CjEgOSA1IDAgOCAwIDAgMCAwPGJyPgowIDcgMCAwIDAgMCAwIDIgNTxicj4KMCAzIDAgNSA3IDkgMSAwIDg8YnI+CjAgMCAwIDYgMCAxIDAgMCAwPGJyPgowIDYgMCA5IDAgMCAwIDAgMTxicj4KMCAwIDAgMCAwIDAgMCAwIDY8L3A+CjwvYmxvY2txdW90ZT4KCjxoMj4K0fnA/crks/YgPHNtYWxsPlNhbXBsZSBPdXRwdXQ8L3NtYWxsPjwvaDI+Cgo8YmxvY2txdW90ZT4KPHA+CqG+yuTI68rks/bR+cD9IDGhvzwvcD4KPHA+CjI4Mjk8L3A+CjxwPgqhvsrkyOvK5LP20fnA/SAxob88L3A+CjxwPgoyODUyPC9wPgo8L2Jsb2NrcXVvdGU+Cgo8aDI+Csr9vt23ts6nvLDM4cq+IDxzbWFsbD5EYXRhIFNpemUgJmFtcDsgSGludDwvc21hbGw+PC9oMj4KCjxibG9ja3F1b3RlPgo8cD4Kob7K/b7dt7bOp6G/PGJyPgo0MCW1xMr9vt2jrMr9tsDW0LfHMCDK/bXEuPbK/bK7ydnT2jMwoaM8YnI+CjgwJbXEyv2+3aOsyv22wNbQt8cwIMr9tcS49sr9srvJ2dPaMjahozxicj4KMTAwJbXEyv2+3aOsyv22wNbQt8cwIMr9tcS49sr9srvJ2dPaMjShozwvcD4KPC9ibG9ja3F1b3RlPgotLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tt9a47s/fLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KPHA+PC9wPgo8cD48YnI+CjwvcD4KPHA+1ebKx9K7tcDJ8cbmtcTL0cv3zOKjobrcyN3S17eiz9ajrNaxvdOxrMvRu+GzrMqxoaOjqLfPu7CjqTwvcD4KPHA+s/3By7zTyc/Su9CpsdjSqrXEuuGhosHQoaK3vSYjMjY2ODQ7tcTF0LbP1q7N4qOsztLP67W9wcvSu7j2uty6w7XEvPTWpqGjo6jG5Mq1yseyzr+8zOK94rXETyihyV+hySlPfn6jqTwvcD4KPHA+z/HJz7TOtcRwcmltZdK70fmjrM7Sw8e/ydLU08XPyMzuxMfQqc/e1saxyL3PtuC1xCYjMjY2ODQ719OhqqGqy/nS1NTasazL0daux7CjrM/I1/bSu8/C1KS0psDto6yw0cO/uPa0/czutcS3vSYjMjY2ODQ7sLTP3tbGtuDJ2cC0xcXQ8qO7yLu687j5vt3Ls9DywLSxrMvRoaM8L3A+CjxwPsi7tvjX1Ly6suLBy9K7z8KjrLeiz9YyMLj2tePW0LOsyrHByzO49rXjo6G/tMC0o6yx2NDru7nSqtPQ0ru49se/09DBprXEvPTWpqGj1tq088WjxtWx6be007O/ydLU08POu9TLy+PTxbuvs6PK/aGivNPJz2lubGluZbvy1d/Kx9PDuPy807jfvLa1xGRhbmNpbmcgbGlua3OhozwvcD4KPHA+zai5/dTZtM7R0L6/zfjJz7XEzOK94qOsztK3os/W19S8urXE1KS0psDt09C1487KzOKho8rUz+ujurWx1dK1vdK7uPbP3tbG1+6087XEMMqxo6y4wyYjMjY2ODQ719O7ubvhttS4w9DQoaK4w8HQoaK4w77FuawmIzI2Njg0O9T2zO3QwrXEz97WxqGj09rKx87S1NrUpLSmwO21xMqxuvK+zdK7tePSu7Xj1dKjrMO/tM7V0rW90ru49s/e1sbX7rTztcQwuvOjrLj80MLP3tbG1NnIpdXSoaM8L3A+CjxwPjg1t9a0+sLro7o8L3A+CjxwPjwvcD4KPHByZSBjbGFzcz0="brush:java;">#include #include #include using namespace std; const int s[10][10]={0,0,0,0,0,0,0,0,0,0,0,1,1,1,2,2,2,3,3,3, 0,1,1,1,2,2,2,3,3,3,0,1,1,1,2,2,2,3,3,3,0,4,4,4,5,5,5,6,6,6, 0,4,4,4,5,5,5,6,6,6,0,4,4,4,5,5,5,6,6,6,0,7,7,7,8,8,8,9,9,9, 0,7,7,7,8,8,8,9,9,9,0,7,7,7,8,8,8,9,9,9}; const int p[10][10]={0,0,0,0,0,0,0,0,0,0,0,6,6,6,6,6,6,6,6,6, 0,6,7,7,7,7,7,7,7,6,0,6,7,8,8,8,8,8,7,6,0,6,7,8,9,9,9,8,7,6, 0,6,7,8,9,10,9,8,7,6,0,6,7,8,9,9,9,8,7,6,0,6,7,8,8,8,8,8,7,6, 0,6,7,7,7,7,7,7,7,6,0,6,6,6,6,6,6,6,6,6}; bool line[10][10],row[10][10],square[10][10]; int xx,yy,n,num,i,j,ans,now,last,cnt,a[10][10]; struct arr{int x,y,z,f[10];}order[100]; bool cmp(arr a,arr b) {return a.z p[b.x][b.y];} inline void get_square(int i,int j) { if (i<=3) xx=1; else if (i<=6) xx=4; else xx=7; if (j<=3) yy=1; else if (j<=6) yy=4; else yy=7; } inline void get_order() { int temp,x,y,max=0,k=0;bool t[10]; for (int i=1;i<=9;i++) for (int j=1;j<=9;j++) if (a[i][j]==0) { memset(t,1,sizeof(t));temp=0; for (xx=1;xx<=9;xx++) if (a[xx][j]>0) t[a[xx][j]]=false; for (yy=1;yy<=9;yy++) if (a[i][yy]>0) t[a[i][yy]]=false; get_square(i,j); for (int i1=xx;i1<=xx+2;i1++) for (int j1=yy;j1<=yy+2;j1++) if (a[i1][j1]>0) t[a[i1][j1]]=false; k++;cnt=0; for (xx=1;xx<=9;xx++) if (t[xx]) {temp++;order[k].f[0]++;order[k].f[order[k].f[0]]=xx;} order[k].x=i;order[k].y=j;order[k].z=temp; } sort(order+1,order+k+1,cmp);num=k; } inline void dfs(int k) { if (k==num+1) { if (now>ans) ans=now; return; } int x=order[k].x;int y=order[k].y; for (int j=1;j<=order[k].f[0];j++) { int i=order[k].f[j]; if (line[x][i]&&row[y][i]&&square[s[x][y]][i]) { now+=i*p[x][y]; line[x][i]=false;row[y][i]=false;square[s[x][y]][i]=false; dfs(k+1); now-=i*p[x][y]; line[x][i]=true;row[y][i]=true;square[s[x][y]][i]=true; } } } int main() { memset(line,1,sizeof(line)); memset(row,1,sizeof(row)); memset(square,1,sizeof(square)); for (i=1;i<=9;i++) for (j=1;j<=9;j++) { scanf("%ld",&a[i][j]); if (a[i][j]>0) { line[i][a[i][j]]=false; row[j][a[i][j]]=false; square[s[i][j]][a[i][j]]=false; last+=a[i][j]*p[i][j]; } } get_order(); ans=-1;dfs(1); if (ans==-1) last=0; printf("%ld\n",ans+last); return 0; }
最后AC代码：

#include
   
    
#include
    
      #include
     
       using namespace std; const int s[10][10]={0,0,0,0,0,0,0,0,0,0,0,1,1,1,2,2,2,3,3,3, 0,1,1,1,2,2,2,3,3,3,0,1,1,1,2,2,2,3,3,3,0,4,4,4,5,5,5,6,6,6, 0,4,4,4,5,5,5,6,6,6,0,4,4,4,5,5,5,6,6,6,0,7,7,7,8,8,8,9,9,9, 0,7,7,7,8,8,8,9,9,9,0,7,7,7,8,8,8,9,9,9}; //这是每个九宫格的预处理。 const int p[10][10]={0,0,0,0,0,0,0,0,0,0,0,6,6,6,6,6,6,6,6,6, 0,6,7,7,7,7,7,7,7,6,0,6,7,8,8,8,8,8,7,6,0,6,7,8,9,9,9,8,7,6, 0,6,7,8,9,10,9,8,7,6,0,6,7,8,9,9,9,8,7,6,0,6,7,8,8,8,8,8,7,6, 0,6,7,7,7,7,7,7,7,6,0,6,6,6,6,6,6,6,6,6}; //分值 bool line[10][10],row[10][10],square[10][10],check[10][10]; int xx,yy,n,num,i,j,ans,k,m,now,last,cnt,a[10][10],f[10][10]; //f就是限制 struct arr{int x,y;}order[100]; //order是枚举顺序。 inline void get_square(int i,int j) //找到当前i,j的九宫格的左上角 { if (i<=3) xx=1; else if (i<=6) xx=4; else xx=7; if (j<=3) yy=1; else if (j<=6) yy=4; else yy=7; } inline void get_order(int k) //每次寻找限制第k多的0的位置 { int max=0,x,y,i,j; for (i=1;i<=9;i++) for (j=1;j<=9;j++) if (check[i][j]&&f[i][j]>max) {max=f[i][j];x=i;y=j;} order[k].x=x;order[k].y=y; for (i=1;i<=9;i++) {f[i][y]++;f[x][i]++;} get_square(x,y); for (i=xx;i<=xx+2;i++) for (j=yy;j<=yy+2;j++) f[i][j]++; check[x][y]=false; } inline void dfs(int k) //容易理解的dfs { if (k==num+1) { if (now>ans) ans=now; return; } int x=order[k].x;int y=order[k].y; for (int i=1;i<=9;i++) if (line[x][i]&&row[y][i]&&square[s[x][y]][i]) { now+=i*p[x][y]; line[x][i]=false;row[y][i]=false;square[s[x][y]][i]=false; dfs(k+1); now-=i*p[x][y]; line[x][i]=true;row[y][i]=true;square[s[x][y]][i]=true; } } int main() { memset(line,1,sizeof(line)); memset(row,1,sizeof(row)); memset(square,1,sizeof(square)); for (i=1;i<=9;i++) for (j=1;j<=9;j++) { scanf("%ld",&a[i][j]); if (a[i][j]>0) { line[i][a[i][j]]=false; row[j][a[i][j]]=false; square[s[i][j]][a[i][j]]=false; last+=a[i][j]*p[i][j]; //原来已经填好的分值 for (k=1;k<=9;k++) { f[i][k]++;f[k][j]++; } get_square(i,j); for (k=xx;k<=xx+2;k++) for (m=yy;m<=yy+2;m++) f[k][m]++; } else {num++;check[i][j]=true;} } for (i=1;i<=num;i++) get_order(i); ans=-1;dfs(1); if (ans==-1) last=0; printf("%ld\n",ans+last); return 0; }