UVa 10957
題目
http://domen111.github.io/UVa-Easy-Viewer/?10957
給一個數獨的盤面，用數字 $0$ ~ $9$ 表示， $0$ 表示該格目前沒有數字
問這個盤面是 有唯一解、有多種解、沒有解，或是一開始的盤面即不符規則
想法
對於每一個當前沒有數字的格子枚舉，把所有符合規則的盤面枚舉出來，計算可行的數量
至於判斷一個盤面是否合法，可以直觀的使用數獨的一般規則來判斷，也就是說
- 一個 $3 \times 3$ 的方格當中只能有 $1$~$9$ 每個數字各一個
- 每一行方格當中只能有 $1$~$9$ 每個數字各一個
- 每一列方格當中只能有 $1$~$9$ 每個數字各一個
可以用三個陣列分別記錄上面三種情況下每個數字出現的次數，只要出現過就不能再枚舉
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
|
#include<iostream>
using namespace std;
int R, ans, Case=1;
int arr[9][9], small_sq[9][10], row[9][10], col[9][10], nxt_x[90], nxt_y[90];
bool check(){
bool res=true;
for(int i=0 ; i<9 ; i++){
for(int j=0 ; j<10 ; j++){
small_sq[i][j] = row[i][j] = col[i][j] = 0;
}
}
for(int i=0 ; i<9 ; i++){
for(int j=0 ; j<9 ; j++){
if(arr[i][j] != 0){
small_sq[3*(i/3)+(j/3)][arr[i][j]]++;
row[i][arr[i][j]]++;
col[j][arr[i][j]]++;
if(small_sq[3*(i/3)+(j/3)][arr[i][j]]>1 || row[i][arr[i][j]] > 1 || col[j][arr[i][j]] > 1)
res=false;
}
}
}
return res;
}
void DFS(int depth){
if(depth == R){
ans++;
if(ans > 1){
return;
}
}
int i = nxt_x[depth];
int j = nxt_y[depth];
for(int k=1 ; k<=9 ; k++){
if(small_sq[3*(i/3)+(j/3)][k]>0 || row[i][k] > 0 || col[j][k] > 0)
continue;
small_sq[3*(i/3)+(j/3)][k]++;
row[i][k]++;
col[j][k]++;
DFS(depth+1);
small_sq[3*(i/3)+(j/3)][k]--;
row[i][k]--;
col[j][k]--;
}
}
int main(){
while(cin>>arr[0][0]){
if(arr[0][0] == 0) nxt_x[0]=0, nxt_y[0]=0, R = 1;
else R = 0;
ans=0;
for(int i=0 ; i<9 ; i++){
for(int j=0 ; j<9 ; j++){
if(i==0 && j==0) continue;
cin>>arr[i][j];
if(arr[i][j] == 0) nxt_x[R]=i, nxt_y[R]=j, R++;
}
}
if(check() == false){
cout<<"Case "<<Case++<<": Illegal.\n";
}
else{
DFS(0);
if(ans == 1){
cout<<"Case "<<Case++<<": Unique.\n";
}
else if(ans > 1){
cout<<"Case "<<Case++<<": Ambiguous.\n";
}
else{
cout<<"Case "<<Case++<<": Impossible.\n";
}
}
}
return 0;
}
|
時間複雜度分析
令 $n = 9$
每筆測資輸入時間複雜度為 $O(n^2)$
每筆測資預處理三種情況時間複雜度為 $O(3n^2)$
DFS 每層最多有 $9$ 種選擇，最多有 $81$ 層
每筆測資 DFS 時間複雜度為 $O(n^{n^2})$
每筆測資總時間複雜度最差為 $O(4n^2 + n^{n^2})$