d352: 10957 - So Doku Checker
Tags :
Accepted rate : 79人/82人 ( 96% ) [非即時]
評分方式:
Tolerant

最近更新 : 2009-07-13 22:17

Content

一個好玩的益智遊戲,通常只是由簡單的點子演變而來的。數獨就是這樣的一個益智遊戲。雖然數獨已經有二十多年的歷史了,然而直到最近幾年,數獨才開始快速的席捲全世界。現今有上百份的報紙和網站,都有在刊載數獨謎題,數獨可以說是每天的活動了。大家應該很好奇數獨到底是什麼,就讓我來做個詳細的介紹:

上面就是一個數獨謎題。大家可以看到盤面呈9x9的方格,其中有些方格填上了1到9之間的數字;此外,盤面也可以看作是呈3x3的大方格(深顏色的線)。數獨的目的,就是要用1到9的數字,填滿所有空白的方格,還要符合下面三個規定:

 ‧每一行都恰有1到9。

 ‧每一列都恰有1到9。

 ‧每個大方格都恰有1到9。

玩數獨時,可以準備紙筆作紀錄,利用消去法逐步推理出答案。當然,數獨也必須設計成可以找出答案。所以一個完善的數獨,必須要符合規定(行、列、大方格之內不能出現同樣的數字)、可以求解(有辦法將所有空白方格填上數字,並且符合規定)、答案要唯一(只有一種解法)。這些都是你的程式要檢查的地方。

Input
輸入包括好幾個數獨謎題,每個謎題佔有9行,每行9個數字,剛好代表一個9x9的盤面,盤面上的空白方格則以0來代替。每個數字之間都會空一格。每個數獨謎題之間都會空一行。
Output

根據輸入的盤面,判斷該數獨謎題是下面四種情形當中的哪一種:

 ‧Illegal,一開始的盤面,就違反了上面那三個規定。

 ‧Unique,只有一種解法。

 ‧Ambiguous,有多種解法。

 ‧Impossible,沒有解法。

然後印出一行判斷結果。輸出格式請參考 Sample Output。

注意:根據上述定義,Illegal同時也會是Impossible,在這種情形下,你的程式只要印出Illegal就好了。當輸入的盤面符合規定,卻無法按照規定填滿方格時,這時候就要印Impossible。

Sample Input
0 0 3 9 0 0 7 6 0
0 4 0 0 0 6 0 0 9
6 0 7 0 1 0 0 0 4
2 0 0 6 7 0 0 9 0
0 0 4 3 0 5 6 0 0
0 1 0 0 4 9 0 0 7
7 0 0 0 9 0 2 0 1
3 0 0 2 0 0 0 4 0
0 2 9 0 0 8 5 0 0
 
0 0 3 9 0 0 7 6 0
0 4 0 0 0 6 0 0 9
6 0 0 0 1 0 0 0 4
0 0 0 6 7 0 0 9 0
0 0 4 0 0 5 6 0 0
0 1 0 0 4 9 0 0 0
7 0 0 0 9 0 2 0 1
3 0 0 2 0 0 0 4 0
0 2 0 0 0 8 5 0 0
 
0 0 3 9 0 0 7 6 0
0 4 0 0 0 6 0 0 9
6 0 7 0 1 0 0 0 4
2 0 0 6 7 0 0 9 0
0 0 4 3 0 5 6 0 0
0 1 0 0 4 9 0 0 7
7 2 0 0 9 0 2 0 1
3 0 0 2 0 0 0 4 0
0 2 9 0 0 8 5 0 0
 
0 0 3 9 0 0 7 6 0
0 4 0 0 0 6 0 0 9
6 0 7 0 1 0 0 0 4
2 0 0 6 7 0 0 9 0
0 0 4 3 0 5 6 0 0
0 1 0 0 4 9 0 0 7
7 5 0 0 9 0 2 0 1
3 0 0 2 0 0 0 4 0
0 2 9 0 0 8 5 0 0
Sample Output
Case 1: Unique.
Case 2: Ambiguous.
Case 3: Illegal.
Case 4: Impossible.
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1M
Hint :
Translated by DJWS
Tags:
出處:
UVa10957 [管理者:
pcsh710742 (ms0472904)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」