UVa 399

UVa 399

題目

http://domen111.github.io/UVa-Easy-Viewer/?399

有一張由 $d \times d$ 塊 $w \times h$ 大小的拼圖,每一塊拼圖的 上、左、下、右 都分別有一個數字

當兩塊拼圖之間的數字只差一個負號的時候(例如: 5-5)這兩塊拼圖就可以放在一起

此外,在四周的拼圖邊上數字都必須是 $0$

舉例來說,我們有這些拼圖

那麼可行的拼法為

想法

因為拼圖有許多拼法,也許兩塊可以組合在一起,但是卻無法拼成完整的拼圖,因此可以考慮窮舉每個當前可行的情況,如果一直拚到最後一塊也沒問題,那就找到答案了

從左至右,從上至下枚舉每一個空格可以放哪些拼圖,檢查邊界、四周的拼圖
除了輸入和判斷比較繁複以外,基本都和 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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
//By Koios1143
#include<iostream>
using namespace std;
int n, d, h, w, res[105][105];
bool used[105], found;
string s;

struct puzzle{
// 拼圖的每一行
string line[30];
// 上左下右四個數字
int above;
int left;
int below;
int right;
}puzzles[105];

bool feasible(int id, int x, int y){
// 當前在邊界,要判斷 0
if(x==1 && puzzles[id].above != 0){
return false;
}
if(y==1 && puzzles[id].left != 0){
return false;
}
if(x==d && puzzles[id].below != 0){
return false;
}
if(y==d && puzzles[id].right != 0){
return false;
}

//right
if(res[x][y+1]!=-1 && puzzles[res[x][y+1]].left != -puzzles[id].right){
return false;
}
//left
if(res[x][y-1]!=-1 && puzzles[res[x][y-1]].right != -puzzles[id].left){
return false;
}
//above
if(res[x-1][y]!=-1 && puzzles[res[x-1][y]].below != -puzzles[id].above){
return false;
}
//below
if(res[x+1][y]!=-1 && puzzles[res[x+1][y]].above != -puzzles[id].below){
return false;
}
return true;
}

void DFS(int depth){
if(depth == d*d){
found=true;
for(int i=1 ; i<=d ; i++){
for(int k=0 ; k<h ; k++){
for(int j=1 ; j<=d ; j++){
cout<<puzzles[res[i][j]].line[k];
}
cout<<"\n";
}
}
return;
}

// x, y 都從 1 開始
// 這樣 res 四周都會是 -1,判斷邊界就不會超出範圍
int x=depth/d+1;
int y=depth%d+1;
for(int i=0 ; i<d*d && !found ; i++){
if(!used[i] && feasible(i, x, y)){
used[i] = true;
res[x][y] = i;
DFS(depth+1);
used[i] = false;
res[x][y] = -1;
}
}
}

int main(){
cin>>n;
for(int t=0 ; t<n ; t++){
if(t) cout<<"\n";

// 初始化
for(int i=0 ; i<30 ; i++){
used[i] = false;
}
for(int i=0 ; i<105 ; i++){
for(int j=0 ; j<105 ; j++){
res[i][j] = -1;
}
}
found = false;

// 輸入
// 要特別注意到,要用 getline 之前如果有 cin,後面都需要一個 getchar 去接收換行
cin>>d>>h>>w;
getchar();
for(int i=0 ; i<d*d ; i++){
// 每塊拼圖之間有一個空行隔開
if(i) getchar();

for(int j=0 ; j<h ; j++){
getline(cin, s);
puzzles[i].line[j] = s;
}
cin>>puzzles[i].above>>puzzles[i].left>>puzzles[i].below>>puzzles[i].right;
getchar();
}
DFS(0);
}

return 0;
}

時間複雜度分析

每筆測資輸入時間複雜度為 $O(d^2hw)$

DFS 每層最多有 $d^2$ 種選擇,共 $d^2$ 層

每筆測資 DFS 時間複雜度為 $O(d^{2^{d^{2}}})$

每筆測資輸出時間複雜度為 $O(d^2hw)$

總時間複雜度為 $O(t(2d^2hw + d^{2^{d^{2}}}))$