題目描述

小城和小華都是熱愛數(shù)學(xué)的好學(xué)生，最近，他們不約而同地迷上了數(shù)獨游戲，好勝的他們想用數(shù)獨來一比高低。但普通的數(shù)獨對他們來說都過于簡單了，于是他們向 Z 博士請教，Z 博士拿出了他最近發(fā)明的“靶形數(shù)獨”，作為這兩個孩子比試的題目。

靶形數(shù)獨的方格同普通數(shù)獨一樣，在?9?格寬×?9?格高的大九宮格中有?9?個?3?格寬×?3?格高的小九宮格（用粗黑色線隔開的）。在這個大九宮格中，有一些數(shù)字是已知的，根據(jù)這些數(shù)字，利用邏輯推理，在其他的空格上填入?1?到?9?的數(shù)字。每個數(shù)字在每個小九宮格內(nèi)不能重復(fù)出現(xiàn)，每個數(shù)字在每行、每列也不能重復(fù)出現(xiàn)。但靶形數(shù)獨有一點和普通數(shù)獨不同，即每一個方格都有一個分值，而且如同一個靶子一樣，離中心越近則分值越高。（如圖）

上圖具體的分值分布是：最里面一格（黃色區(qū)域）為?10?分，黃色區(qū)域外面的一圈（紅色區(qū)域）每個格子為?9?分，再外面一圈（藍色區(qū)域）每個格子為?8?分，藍色區(qū)域外面一圈（棕色區(qū)域）每個格子為?7?分，最外面一圈（白色區(qū)域）每個格子為?6?分，如上圖所示。比賽的要求是：每個人必須完成一個給定的數(shù)獨（每個給定數(shù)獨可能有不同的填法），而且要爭取更高的總分數(shù)。而這個總分數(shù)即每個方格上的分值和完成這個數(shù)獨時填在相應(yīng)格上的數(shù)字的乘積的總和

總分數(shù)即每個方格上的分值和完成這個數(shù)獨時填在相應(yīng)格上的數(shù)字的乘積的總和。如圖，在以下的這個已經(jīng)填完數(shù)字的靶形數(shù)獨游戲中，總分數(shù)為 2829。游戲規(guī)定，將以總分數(shù)的高低決出勝負。

由于求勝心切，小城找到了善于編程的你，讓你幫他求出，對于給定的靶形數(shù)獨，能夠得到的最高分數(shù)。

輸入輸出格式

輸入格式：

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

輸出格式：

輸出共?1?行。輸出可以得到的靶形數(shù)獨的最高分數(shù)。如果這個數(shù)獨無解，則輸出整數(shù)?-1?。

輸入輸出樣例

輸入樣例#1：

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

輸出樣例#1：

2829

輸入樣例#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

輸出樣例#2：

2852

源代碼

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #include<set> #include<map> #include<stack> #include<vector> #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 11 #define MOD 123 #define E 1e-6 using namespace std; int g[N][N]; int grade[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}, }; int area[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}, }; struct Node{int x;int y; }point[N*10]; int vis_x[N][N],vis_y[N][N],vis_g[N][N]; int vis[N*10]; int n,sum; void dfs(int k) {if(k>n)//當(dāng)確定的數(shù)字個數(shù)大于未填入的數(shù)字總數(shù)時{int cnt=0;for(int i=1;i<=9;i++)//記錄分值for(int j=1;j<=9;j++)cnt+=g[i][j]*grade[i][j];sum=max(sum,cnt);//取最大分值return;}int w=INF,temp;for(int i=1;i<=n;i++)//確定搜索的起點if(!vis[i]){int ww=0;for(int j=1;j<=9;j++)if( !vis_x[point[i].x][j] && !vis_y[point[i].y][j] && !vis_g[area[point[i].x][point[i].y]][j] )if(++ww==w)break;if(ww<w){w=ww;temp=i;}}vis[temp]=1;int x=point[temp].x;int y=point[temp].y;for(int i=1;i<=9;i++)//枚舉每一層可能的狀態(tài)if( !vis_x[x][i] && !vis_y[y][i] && !vis_g[area[x][y]][i] )//如果當(dāng)前數(shù)字在整個圖的橫向縱向小區(qū)域內(nèi)未出現(xiàn)過{g[x][y]=i;vis_x[x][i]=1;vis_y[y][i]=1;vis_g[area[x][y]][i]=1;dfs(k+1);vis_x[x][i]=0;vis_y[y][i]=0;vis_g[area[x][y]][i]=0;}vis[temp]=0; } int main() {n=0;for(int i=1;i<=9;i++)for(int j=1;j<=9;j++){cin>>g[i][j];if(g[i][j])//如果當(dāng)前點填入數(shù)字{vis_x[i][g[i][j]]=1;//標記該行vis_y[j][g[i][j]]=1;//標記該列vis_g[area[i][j]][g[i][j]]=1;//標記整張圖}else//如果當(dāng)前點未填入數(shù)字{/*記錄未填入數(shù)字*/n++;point[n].x=i;point[n].y=j;}}sum=-1;dfs(1);cout<<sum<<endl;return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的靶形数独（洛谷-P1074）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。