P1074 靶形數(shù)獨(dú)

• • 318通過
  • 1.5K提交
• 題目提供者洛谷OnlineJudge
• 標(biāo)簽搜索/枚舉2009NOIp提高組
• 難度提高+/省選-

提交該題?討論?題解?記錄

題目描述

小城和小華都是熱愛數(shù)學(xué)的好學(xué)生，最近，他們不約而同地迷上了數(shù)獨(dú)游戲，好勝的他

們想用數(shù)獨(dú)來一比高低。但普通的數(shù)獨(dú)對他們來說都過于簡單了，于是他們向 Z 博士請教，

Z 博士拿出了他最近發(fā)明的“靶形數(shù)獨(dú)”，作為這兩個孩子比試的題目。

靶形數(shù)獨(dú)的方格同普通數(shù)獨(dú)一樣，在 9 格寬×9 格高的大九宮格中有 9 個 3 格寬×3 格

高的小九宮格（用粗黑色線隔開的）。在這個大九宮格中，有一些數(shù)字是已知的，根據(jù)這些數(shù)字，利用邏輯推理，在其他的空格上填入 1 到 9 的數(shù)字。每個數(shù)字在每個小九宮格內(nèi)不能

重復(fù)出現(xiàn)，每個數(shù)字在每行、每列也不能重復(fù)出現(xiàn)。但靶形數(shù)獨(dú)有一點(diǎn)和普通數(shù)獨(dú)不同，即

每一個方格都有一個分值，而且如同一個靶子一樣，離中心越近則分值越高。（如圖）

上圖具體的分值分布是：最里面一格（黃色區(qū)域）為 10 分，黃色區(qū)域外面的一圈（紅

色區(qū)域）每個格子為 9 分，再外面一圈（藍(lán)色區(qū)域）每個格子為 8 分，藍(lán)色區(qū)域外面一圈（棕

色區(qū)域）每個格子為 7 分，最外面一圈（白色區(qū)域）每個格子為 6 分，如上圖所示。比賽的

要求是：每個人必須完成一個給定的數(shù)獨(dú)（每個給定數(shù)獨(dú)可能有不同的填法），而且要爭取

更高的總分?jǐn)?shù)。而這個總分?jǐn)?shù)即每個方格上的分值和完成這個數(shù)獨(dú)時填在相應(yīng)格上的數(shù)字

的乘積的總和

總分?jǐn)?shù)即每個方格上的分值和完成這個數(shù)獨(dú)時填在相應(yīng)格上的數(shù)字

的乘積的總和。如圖，在以下的這個已經(jīng)填完數(shù)字的靶形數(shù)獨(dú)游戲中，總分?jǐn)?shù)為 2829。游戲規(guī)定，將以總分?jǐn)?shù)的高低決出勝負(fù)。

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

夠得到的最高分?jǐn)?shù)。

輸入輸出格式

輸入格式：

?

一共 9 行。每行 9 個整數(shù)（每個數(shù)都在 0―9 的范圍內(nèi)），表示一個尚未填滿的數(shù)獨(dú)方

格，未填的空格用“0”表示。每兩個數(shù)字之間用一個空格隔開。

?

輸出格式：

?

輸出文件 sudoku.out 共 1 行。

輸出可以得到的靶形數(shù)獨(dú)的最高分?jǐn)?shù)。如果這個數(shù)獨(dú)無解，則輸出整數(shù)-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 2sudoku2 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 2829sudoku2 2852

說明

【數(shù)據(jù)范圍】

40%的數(shù)據(jù)，數(shù)獨(dú)中非 0 數(shù)的個數(shù)不少于 30。

80%的數(shù)據(jù)，數(shù)獨(dú)中非 0 數(shù)的個數(shù)不少于 26。

100%的數(shù)據(jù)，數(shù)獨(dú)中非 0 數(shù)的個數(shù)不少于 24。

NOIP 2009 提高組 第四題

分析：對于這道題，首先想到的就是搜索，但是數(shù)據(jù)太大，絕對TLE,這個時候就要用一些特殊的技巧.如果我們自己來做數(shù)獨(dú)題，會怎么做呢?一定會先填可選數(shù)字最少的那一格吧。搜索的順序也是這樣，每次都搜能填個數(shù)最少的那一格，就可以過了.這里有個小技巧就是怎么表示每個九宮格，具體看代碼.

#include <cstdio> #include <cmath> #include <cstring> #include <iostream> #include <algorithm>using namespace std; int a[10][10],fenshu[10][10],vis1[30][10],vis2[10][10],vis3[10][10],b[10][10],ans = -1;void dfs() {int x,y,step = 10;for (int i = 1; i <= 9; i++)for (int j = 1; j <= 9; j++){if (!a[i][j]){int s = 0;for (int k = 1; k <= 9; k++) if (!vis1[b[i][j]][k] && !vis2[i][k] && !vis3[j][k])s++;if (s < step){step = s;x = i;y = j;}}}if (step == 10) {int k = 0;for (int i = 1; i <= 9; i++)for (int j = 1; j <= 9; j++)k += a[i][j] * fenshu[i][j];ans = max(ans,k); }for (int k = 1; k <= 9; k++)if (!vis1[b[x][y]][k] && !vis2[x][k] && !vis3[y][k]){vis1[b[x][y]][k] = vis2[x][k] = vis3[y][k] = 1;a[x][y] = k;dfs();a[x][y] = 0;vis1[b[x][y]][k] = vis2[x][k] = vis3[y][k] = 0;} }int main() {memset(vis1,0,sizeof(vis1));memset(vis2,0,sizeof(vis2));memset(vis3,0,sizeof(vis3));for (int i = 1; i <= 9; i++)for (int j = 1; j <= 9; j++){scanf ("%d",&a[i][j]); fenshu[i][j] = 10 - max(abs(i - 5),abs(j - 5));b[i][j] = (i - 1) / 3 * 3 + (j - 1) / 3 + 1;vis1[b[i][j]][a[i][j]] = 1;vis2[i][a[i][j]] = 1;vis3[j][a[i][j]] = 1; } dfs();printf("%d",ans);return 0; }

codevs數(shù)據(jù)良心，洛谷坑爹！

轉(zhuǎn)載于:https://www.cnblogs.com/zbtrs/p/5715422.html

總結(jié)

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

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