UVa 989
題目
http://domen111.github.io/UVa-Easy-Viewer/?989
跟數獨問題相同，不過這次的版面大小可以從 $1 \times 1$ 到 $3 \times 3$
想法
記錄小正方形、行、列每個數字是否出現過，透過 DFS 枚舉每種可能
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
|
#include<iostream>
using namespace std;
int n, R, arr[9][9], nx[81], ny[81];
bool found, out=false, small_sq[9][10], row[9][10], col[9][10];
void init(){
for(int i=0 ; i<9 ; i++){
for(int j=0 ; j<10 ; j++){
small_sq[i][j] = false;
row[i][j] = false;
col[i][j] = false;
}
}
for(int i=0 ; i<n*n ; i++){
for(int j=0 ; j<n*n ; j++){
if(arr[i][j] != 0){
col[j][arr[i][j]]=true;
row[i][arr[i][j]]=true;
small_sq[n*(i/n) + j/n][arr[i][j]]=true;
}
}
}
}
void DFS(int depth){
if(depth == R){
found = true;
for(int i=0 ; i<n*n ; i++){
for(int j=0 ; j<n*n ; j++){
if(j) cout<<' ';
cout<<arr[i][j];
}
cout<<'\n';
}
return;
}
int x = nx[depth];
int y = ny[depth];
for(int i=1 ; i<=n*n && !found ; i++){
if(!col[y][i] && !row[x][i] && !small_sq[n*(x/n) + y/n][i]){
col[y][i] = true;
row[x][i] = true;
small_sq[n*(x/n) + y/n][i] = true;
arr[x][y] = i;
DFS(depth+1);
col[y][i] = false;
row[x][i] = false;
small_sq[n*(x/n) + y/n][i] = false;
arr[x][y] = 0;
}
}
}
int main(){
while(cin>>n){
if(out) cout<<"\n";
else out=true;
R = 0;
found = false;
for(int i=0 ; i<n*n ; i++){
for(int j=0 ; j<n*n ; j++){
cin>>arr[i][j];
if(arr[i][j] == 0){
nx[R] = i;
ny[R] = j;
R++;
}
}
}
init();
DFS(0);
if(!found){
cout<<"NO SOLUTION\n";
}
}
return 0;
}
|
時間複雜度分析
每筆測資輸入時間複雜度為 $O(n^2 \times n^2)$
DFS 每次最多有 $n^2$ 種選擇，最多有 $n^2 \times n^2$ 層
每筆測資 DFS 時間複雜度為 $O(n^{2^{n^{4}}})$
每筆測資總時間複雜度為 $O(n^4 + n^{2^{n^{4}}})$