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
| #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){ 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; } if(res[x][y+1]!=-1 && puzzles[res[x][y+1]].left != -puzzles[id].right){ return false; } if(res[x][y-1]!=-1 && puzzles[res[x][y-1]].right != -puzzles[id].left){ return false; } if(res[x-1][y]!=-1 && puzzles[res[x-1][y]].below != -puzzles[id].above){ return false; } 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; } 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; 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}}}))$