# 演算法課程題解 - DFS
# UVa 441
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?441
給一個正整數 $k$ 以及 $k$ 個由小到大排序好的數字，輸出所有序列長度為 $6$ 的組合，所有組合皆由小到大輸出
$6 < k < 13$
## 想法 By Koios
因為題目要求組合而非排列，所以說像是 $(1, 2, 3)$ 和 $(2, 1, 3)$ 會被視為相同的
所以我們可以這麼想，這些會被視為相同的組合在由小到大排序過後都是一樣的
所以我們可以直接找那個由小到大嚴格遞增的那個，在上例中就是 $(1, 2, 3)$
既然 $k$ 不大，我們就可以考慮使用 DFS 去枚舉出所有的狀況
並且為了保持每個組合的遞增性，記錄上次最後存取的元素位置，下次就只能從那個位置之後繼續枚舉
例如說給定的序列是 $\{1, 2, 3, 4\}$
現在枚舉到 $\{1, 3\}$ 的時候，下次就不需要再看 $3$ 以前的數字了，只需要看 $3$ 以後的數字
如此一來，我們就可以在維持序列遞增性的前提下去枚舉出所有情況了!
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
int n, m, tmp[6], arr[15], res[10];
void dfs(int depth, int start){
// 已經找好六個數字了
if(depth == 6){
// 把結果複製到 tmp
for(int i=0 ; i<6 ; i++){
tmp[i] = res[i];
}
for(int i=0 ; i<6 ; i++){
if(i) cout<<" ";
cout<<tmp[i];
}
cout<<"\n";
return;
}
// 從 start 開始枚舉
for(int i=start ; i<n ; i++){
res[depth] = arr[i];
dfs(depth+1, i+1);
}
}
int main(){
bool out=false;
while(cin>>n && n){
if(out) cout<<"\n";
else out=true;
for(int i=0 ; i<n ; i++){
cin>>arr[i];
}
dfs(0, 0);
}
return 0;
}
```
### 時間複雜度分析
每筆測資輸入時間複雜度為 $O(n)$
DFS 每一層最多會有 $n$ 個選擇，總共有 $6$ 層
每筆測資 DFS 時間複雜度為 $O(n^6)$
每筆測資總時間複雜度約為 $O(n^7)$
# UVa 216
http://domen111.github.io/UVa-Easy-Viewer/?216
在平面座標上有 $n$ 個點，我們要用 $n-1$ 條網路線連接這 $n$ 個點
為了安裝方便，兩台電腦之間會多預留 $16$ 呎的網路線
是否能找到一種連接方式，使得電腦都有網路線連接，並且網路線總長度最少
$2 \leq n \leq 8$
## 想法 By Koios
這一題的 $n$ 很小，所以我們可以考慮比較暴力的作法
任意選擇一個起點，然後往下任意選擇下一個點，一直做到每個點都選擇到了，然後計算長度，把當前最短的長度所經過的點都記錄下來
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;
int n, Case=1, x[10], y[10], tmpx[10], tmpy[10], rx[10], ry[10];
bool used[10];
double tot, min_dis;
// 計算兩點之間距離
double dist(int p, int q, int m, int n){
return sqrt(pow(p-m, 2) + pow(q-n, 2));
}
// path 紀錄當前網路線總長度
void dfs(int depth, double path){
if(depth == n){
if(path < min_dis){
min_dis = path;
// 紀錄當前長度最短的路徑
for(int i=0 ; i<n ; i++){
rx[i] = tmpx[i];
ry[i] = tmpy[i];
}
}
return;
}
for(int i=0 ; i<n ; i++){
if(!used[i]){
used[i] = true;
tmpx[depth] = x[i];
tmpy[depth] = y[i];
if(depth == 0) dfs(depth+1, 0);
else dfs(depth+1, path+dist(tmpx[depth], tmpy[depth], tmpx[depth-1], tmpy[depth-1])+16);
used[i] = false;
}
}
}
int main(){
while(cin>>n && n){
// 初始化最小值是一個極大值
min_dis=2147483647;
for(int i=0 ; i<n ; i++){
cin>>x[i]>>y[i];
used[i] = false;
}
dfs(0, 0);
cout<<"**********************************************************\n";
cout<<"Network #"<<Case++<<"\n";
for(int i=1 ; i<n ; i++){
cout<<"Cable requirement to connect ("<<rx[i-1]<<","<<ry[i-1]<<") to ("<<rx[i]<<","<<ry[i]<<") is "<<fixed<<setprecision(2)<<dist(rx[i-1], ry[i-1], rx[i], ry[i])+16<<" feet.\n";
}
cout<<"Number of feet of cable required is "<<min_dis<<".\n";
}
return 0;
}
```
### 時間複雜度分析
每筆測資輸入時間複雜度為 $O(n)$
DFS 每一層最多有 $n$ 種選擇，總共有 $n$ 層，並且最後一層需要 $O(n)$ 的時間複製當前答案
每筆測資 DFS 時間複雜度為 $O(n^n \times n) = O(n^{n+1})$
每筆測資總時間複雜度約為 $O(n^{n+2})$
# UVa 11084
http://domen111.github.io/UVa-Easy-Viewer/?11084
給一個只由數字組成的字串 $s$ 以及一個數字 $t$，問在 $s$ 的所有排列當中有多少個數字可以被 $t$ 整除
$1 \leq |s| \leq 10\\
1 \leq d \leq 10^4$
## 想法 By Koios
由於這題的 $|s|$ 不大，可以考慮比較暴力的做法
直接利用 DFS 去枚舉出所有的排列，接著去計算是否能整除
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int t, d, n;
long long ans=0;
bool used[15];
string s;
void dfs(int depth, string res){
if(depth == n){
long long cnt=0;
for(int i=0 ; i<n ; i++){
cnt*=10;
cnt+=res[i]-'0';
}
if(cnt % d == 0) ans++;
return;
}
bool num_used[15];
for(int i=0 ; i<15 ; i++) num_used[i] = false;
for(int i=0 ; i<n ; i++){
if(!used[i] && !num_used[s[i]-'0']){
used[i] = true;
num_used[s[i]-'0'] = true;
dfs(depth+1, res+s[i]);
used[i] = false;
}
}
}
int main(){
cin>>t;
while(t--){
ans=0;
for(int i=0 ; i<15 ; i++){
used[i] = false;
}
cin>>s>>d;
n = s.size();
dfs(0, "");
cout<<ans<<"\n";
}
return 0;
}
```
### 時間複雜度分析
每筆測資輸入時間複雜度為 $O(|s|)$
DFS 每一層最多有 $|s|$ 種選擇，並且有 $|s|$ 層，令 $n = |s|$
每筆測資 DFS 時間複雜度為 $n^n$
總時間複雜度為 $O(tn^{n+1})$
# UVa 10776
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?10776
本題有多筆測資，每筆測資包含一個字串 $s$ 以及一個數字 $r$，求以 $s$ 為集合，所有長度為 $r$ 的字串組合，每個輸出字串由小到大排列
## 想法 By Koios
因為要求的是組合，我們可以去枚舉答案的第 $i$ 格要是什麼，並且過去枚舉過的字就不能再使用
為了避免重複枚舉到重複的字串，一開始要先把字串由小到大排序好
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
string s, res[35];
int n;
void DFS(int depth, int start){
// 枚舉完 n 個字了
if(depth == n){
for(int i=0 ; i<n ; i++){
cout<<res[i];
}
cout<<"\n";
return;
}
// 第 i 個字不能重複
// 用 used 紀錄用過的字
bool used[26];
for(int i=0 ; i<26 ; i++){
used[i] = false;
}
// 前面娶過的字不會再被用到
// 從 start 開始枚舉
for(int i=start ; i<s.size() ; i++){
if(!used[s[i]-'a']){
used[s[i]-'a']=true;
res[depth] = s[i];
DFS(depth+1, i+1);
}
}
}
int main(){
while(cin>>s>>n){
sort(s.begin(), s.end());
DFS(0, 0);
}
return 0;
}
```
### 時間複雜度分析
每筆測資輸入時間複雜度為 $O(|s|)$，令 $n = |s|$
每筆測資排序時間複雜度為 $O(nlogn)$
DFS 每一層最多有 $|s|$ 種選擇，總共有 $|s|$ 層
每筆測資 DFS 時間複雜度為 $O(n^n)$
每筆測資總時間複雜度為 $O(nlogn + n^{n+1})$
# UVa 167
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?167
在一個 $8 \times 8$ 的西洋棋棋盤上要放上 $8$ 個皇后，並且所有皇后之間彼此不能在對方的攻擊範圍內，也就是經典的 $8$ 皇后問題
現在在棋盤上的每個格子都有一個數字，求所有符合 $8$ 皇后的情況下，所有皇后所在的格子數字總和最大是多少
## 想法 By Koios
因為棋盤大小固定只有 $8 \times 8$，可以考慮用比較暴力的方式去做
枚舉每一橫排的皇后可以存在的位置，直到所有橫排都枚舉完後記錄當前的數字總和並記錄下最大的情況
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
#include<iomanip>
using namespace std;
int arr[8][8], path_x[8], path_y[8], k, ans;
void dfs(int depth){
if(depth == 8){
int tot=0;
// 計算當前數字總和
for(int i=0 ; i<8 ; i++){
tot += arr[path_x[i]][path_y[i]];
}
// 找出最大值
ans=max(ans, tot);
return;
}
// 對於橫排的 8 個位置枚舉
for(int i=0 ; i<8 ; i++){
bool cango = true;
// 檢查 depth 排以前的皇后與現在的位置是否衝突
for(int j=0 ; j<depth ; j++){
// 檢查是否在同一列上
if(path_y[j] == i){
cango=false;
break;
}
// 檢查是否在同一斜線上
if(abs(path_x[j]-depth) == abs(path_y[j]-i)){
cango=false;
break;
}
}
if(cango){
path_x[depth] = depth;
path_y[depth] = i;
dfs(depth+1);
}
}
}
int main(){
cin>>k;
while(k--){
ans=0;
for(int i=0 ; i<8 ; i++){
for(int j=0 ; j<8 ; j++){
cin>>arr[i][j];
}
}
dfs(0);
// 輸出格式須符合總長度為 5，不足則以空格補齊
cout<<setw(5)<<ans<<"\n";
}
return 0;
}
```
### 時間複雜度分析
令 $n = 8$
每筆測資輸入時間複雜度為 $O(n^2)$
DFS 每層最多有 $8$ 種選擇，總共有 $8$ 層
每筆測資 DFS 時間複雜度為 $O(n^n)$
總時間複雜度為 $O(kn^{n+2})$
# UVa 10957
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?10957
給一個數獨的盤面，用數字 $0$ ~ $9$ 表示， $0$ 表示該格目前沒有數字
問這個盤面是 **有唯一解**、**有多種解**、**沒有解**，或是一開始的盤面即不符規則
## 想法 By Koios
對於每一個當前沒有數字的格子枚舉，把所有符合規則的盤面枚舉出來，計算可行的數量
至於判斷一個盤面是否合法，可以直觀的使用數獨的一般規則來判斷，也就是說
1. 一個 $3 \times 3$ 的方格當中只能有 $1$~$9$ 每個數字各一個
2. 每一行方格當中只能有 $1$~$9$ 每個數字各一個
3. 每一列方格當中只能有 $1$~$9$ 每個數字各一個
可以用三個陣列分別記錄上面三種情況下每個數字出現的次數，只要出現過就不能再枚舉
### 程式碼
```cpp=
//By Koios1143
#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){
// 3*3 方格從左至右、從上至下依序編號 1~9
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]){
// R 記錄空格子的數量
// nxt_x, nxt_y 記錄空格的座標
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})$
# TIOJ 1235
## 題目
https://tioj.ck.tp.edu.tw/problems/1235
跟數獨問題相同，不過這次從數字改成英文字母，保證一定有解的前提下，輸出每個空格應該是哪個對應的英文字母
**無論那一行是否有空格，都需要有一個換行**
## 想法 By Koios
跟數獨問題相同，我們可以枚舉每個空格可行的數字，枚舉到每個格子都填滿就可以輸出答案了
為了方便處理，我們可以把每個英文字母對應到一個數字，接下來就跟數獨問題一樣了
跟數獨一樣有三種情況
1. 一個 $3 \times 3$ 的方格當中只能有 $1$~$9$ 每個數字各一個
2. 每一行方格當中只能有 $1$~$9$ 每個數字各一個
3. 每一列方格當中只能有 $1$~$9$ 每個數字各一個
先計算出每種情況中每個數字出現的數字，就可以用來判斷某個數字是否能被放在空格當中
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int R, ans, Case=1;
int small_sq[9][10], row[9][10], col[9][10], nxt_x[90], nxt_y[90];
char arr[9][9];
// 建立英文與數字的對應表
string color="ROYGBIPLW";
int color_num[30];
char num_color[10];
bool found=false;
void init(){
// 統計三種情況中每個數字出現的次數
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] != '*'){
small_sq[3*(i/3)+(j/3)][color_num[arr[i][j]-'A']]++;
row[i][color_num[arr[i][j]-'A']]++;
col[j][color_num[arr[i][j]-'A']]++;
}
}
}
}
void DFS(int depth){
if(depth == R){
for(int i=0, k=0, x, y ; i<9 ; i++){
for(int j=0 ; j<9 ; j++){
x = nxt_x[k];
y = nxt_y[k];
if(i==x && j==y){
cout<<arr[i][j];
k++;
}
}
cout<<'\n';
}
found=true;
}
int i = nxt_x[depth];
int j = nxt_y[depth];
for(int k=1 ; k<=9 && !found ; 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]++;
arr[i][j] = num_color[k];
DFS(depth+1);
small_sq[3*(i/3)+(j/3)][k]--;
row[i][k]--;
col[j][k]--;
arr[i][j] = '*';
}
}
int main(){
// 建立英文與數字的對應表
for(int i=1 ; i<=color.size() ; i++){
num_color[i] = color[i-1];
color_num[color[i-1]-'A'] = i;
}
R=0;
ans=0;
for(int i=0 ; i<9 ; i++){
for(int j=0 ; j<9 ; j++){
cin>>arr[i][j];
if(arr[i][j] == '*') nxt_x[R]=i, nxt_y[R]=j, R++;
}
}
init();
DFS(0);
return 0;
}
```
# TOJ 362
## 題目
https://toj.tfcis.org/oj/pro/362/
現在有一副撲克牌，分成 $4$ 堆，每一堆都有 $13$ 張牌
現在我們要從 $4$ 個牌堆當中每次選兩張相同的拿出，最後是否有辦法把全部的牌拿完?
## 想法 By Koios
我們可以枚舉在每一層當前的 $4$ 張牌當中要取哪兩張，把所有的情況列出，如果能將全部的牌取完就表示有答案，否則沒有
至於要如何知道牌堆中哪張牌是最上方的，我們可以用一個陣列去紀錄 $4$ 個牌堆最上方的牌是牌堆中的第幾張，如此一來要枚舉的時候就只需要改變紀錄的 index 即可
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int arr[4][13];
int top[4];
bool found=false, ans=false;
void DFS(int depth){
if(depth == 26){
ans=true;
found=true;
return;
}
for(int i=0 ; i<4 ; i++){
for(int j=i+1 ; j<4 && !found ; j++){
if(top[i]<13 && top[j]<13 && arr[i][top[i]] == arr[j][top[j]]){
top[i]++;
top[j]++;
DFS(depth+1);
top[i]--;
top[j]--;
}
}
}
}
int main(){
for(int i=0 ; i<4 ; i++){
top[i] = 0;
for(int j=0 ; j<13 ; j++){
cin>>arr[i][j];
}
}
DFS(0);
if(ans){
cout<<"YES\n";
}
else{
cout<<"NO\n";
}
return 0;
}
```
### 時間複雜度分析
令 $n = 4, m = 13$
輸入時間複雜度為 $O(nm)$
DFS 每層最多有 $4$ 種選擇，總共有 $26$ 層
DFS 時間複雜度為 $O(n^{2m})$
總時間複雜度為 $O(nm + n^{2m})$
# UVa 124
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?124
給你幾個不重複的小寫英文字母，告訴你某些字母之間的大小關係，把所有從小到大的排列列出來
如果沒有告知某個元素的大小關係，那可以任意擺放
## 想法1 By Koios
我們可以紀錄兩個元素之間的關係，兩兩元素間的關係可以分成 `a<b` `a>b` `未定義` 三種
只要當前枚舉的元素跟前面的元素彼此之間不衝突，也就是說並不是 `a>b` 的狀態就可以枚舉下去
因為要找出所有情況，所以枚舉方式是採用 DFS
### 程式碼
```cpp=
#include<iostream>
#include<sstream>
using namespace std;
int var_nums, tbl[26];
int less_than[26][26]; // 0: undefine, 1: less, 2: larger or others
string vars, cons;
char v, x, y, res[26];
bool out=false, used_vars[26];
void DFS(int depth){
if(depth == var_nums){
for(int i=0 ; i<depth ; i++){
cout<<res[i];
}
cout<<"\n";
return;
}
for(int i=0 ; i<26 ; i++){
if(tbl[i]){
bool less=true;
for(int j=0 ; j<depth ; j++){
// 只要出現大於的情況就避開
if(less_than[res[j]-'a'][i]==2){
less=false;
}
}
if(less){
res[depth] = i+'a';
DFS(depth+1);
}
}
}
}
int main(){
while(getline(cin, vars)){
if(out) cout<<'\n';
else out=true;
// 初始化
var_nums=0;
for(int i=0 ; i<26 ; i++){
tbl[i] = 0;
used_vars[i] = false;
for(int j=0 ; j<26 ; j++){
less_than[i][j] = 2;
}
}
stringstream ss;
ss<<vars;
while(ss>>v){
tbl[v-'a']++;
var_nums++;
used_vars[v-'a'] = true;
}
// 預設把所有元素之間的關係都設成未定義
for(int i=0 ; i<26 ; i++){
if(!tbl[i]) continue;
for(int j=0 ; j<26 ; j++){
if(!tbl[j]) continue;
if(i != j)
less_than[i][j] = 0;
}
}
getline(cin, cons);
// 重設 stringstream
ss.str("");
ss.clear();
ss<<cons;
while(ss>>x>>y){
less_than[x-'a'][y-'a'] = 1;
less_than[y-'a'][x-'a'] = 2;
}
DFS(0);
}
return 0;
}
```
## 想法2 By Koios
既然題目給的是兩兩之間的關係，那麼就可以想到用一個圖來表示
例如題目的第一筆測資
那麼該怎麼枚舉呢?隨便選一個點走下去嗎?
從上圖可以發現到，因為 $G$ 跟其他點的大小關係是未定義的，所以我們永遠走不到它，所以要換個想法
如果當前連到點 $x$ 的線數量是 $0$ ，就表示我們可以選擇這個點
在選擇 $x$ 之後，我們需要把 $x$ 以及 $x$ 所能連接到的所有點的邊砍斷
如此一來，與 $x$ 相連的所有點在下一次都是可以枚舉的點了!
並且我們不會忽略那些未定義的點
這個方法被稱為拓樸排序，也會用到 DFS 的概念
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
#include<sstream>
using namespace std;
string vars, cons;
char v, x, y, res[26];
bool out=false, nxt[26][26];
int var_nums, tbl[26], in[26];
void DFS(int depth){
if(depth == var_nums){
for(int i=0 ; i<depth ; i++){
cout<<res[i];
}
cout<<"\n";
return;
}
for(int i=0 ; i<26 ; i++){
if(tbl[i] && in[i]==0){
res[depth] = i+'a';
// 刪除當前以及下一層點的邊
// 刪除當前是為了避免下次被重複枚舉
in[i]--;
for(int j=0 ; j<26 ; j++){
if(tbl[j] && nxt[i][j]){
in[j]--;
}
}
DFS(depth+1);
in[i]++;
for(int j=0 ; j<26 ; j++){
if(tbl[j] && nxt[i][j]){
in[j]++;
}
}
}
}
}
int main(){
while(getline(cin, vars)){
if(out) cout<<"\n";
else out=true;
// 初始化
var_nums=0;
for(int i=0 ; i<26 ; i++){
tbl[i] = in[i] = 0;
for(int j=0 ; j<26 ; j++){
nxt[i][j] = false;
}
}
stringstream ss;
ss<<vars;
while(ss>>v){
tbl[v-'a']=1;
var_nums++;
}
getline(cin, cons);
ss.str("");ss.clear();
ss<<cons;
while(ss>>x>>y){
// 連結到 y 的邊 +1
in[y-'a']++;
// 記錄下邊是存在的
nxt[x-'a'][y-'a'] = true;
}
DFS(0);
}
return 0;
}
```
# UVa 258
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?258
給一個 $n \times m$ 的方格，在最外圍保證只有兩個點是 `.`，表示起點以及終點，其餘都是 `*`
起點會有一束光源源不絕射入，如果遇到地圖當中的鏡子 `/` 或是 `\` 就會被反射，這裡的鏡子都會是以 $45^{\circ}$ 放置，也就是說光會轉向 $90^{\circ}$
每個鏡子都可以選擇要是 `/` 或是 `\`，輸出其中一組可以使光照射出終點的盤面
## 想法 By Koios
首先先找到起點以及終點，因為是光所以其實起點終點相反也沒關係
再來對於光來說方向也是重要的狀態，所以也同時先找到起點光射入的方向
找到之後嘗試跟著方向走，如果遇到鏡子就分成兩種情況
1. 跟著鏡子反射，然後固定這個鏡子的方向
2. 如果之前沒有光線經過這個鏡子，那我們就嘗試轉方向
這裡很重要的是要記錄這個鏡子有沒有被光線走過，如果有光線經過而我們又調整鏡子的方向，可能會導致光線不會走到現在的點上
那麼一直走到出口就找到答案了
因為每次都是一路走到底，所以可以用 DFS 去嘗試每種走法
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
// 0: up , 1: right, 2: down, 3: left
int n ,m, start_x, start_y, end_x, end_y, start_dir, end_dir, nx, ny, n_dir;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
char arr[55][55];
bool used[55][55], out=false, found;
void DFS(int x, int y, int dir){
if(found) return;
if(x==end_x && y==end_y){
found=true;
for(int i=0 ; i<n ; i++){
for(int j=0 ; j<m ; j++){
cout<<arr[i][j];
}
cout<<"\n";
}
return;
}
if(arr[x][y] == '.'){
nx = x + dx[dir];
ny = y + dy[dir];
DFS(nx, ny, dir);
}
else if(arr[x][y] == '*'){
return;
}
else{
if(arr[x][y] == '/'){
bool tmp=used[x][y];
used[x][y] = true;
n_dir = dir^1;
nx = x + dx[n_dir];
ny = y + dy[n_dir];
DFS(nx, ny, n_dir);
used[x][y] = tmp;
// spin mirror
if(!used[x][y]){
used[x][y] = true;
arr[x][y] = '\\';
n_dir = 3-dir;
nx = x + dx[n_dir];
ny = y + dy[n_dir];
DFS(nx, ny, n_dir);
arr[x][y] = '/';
used[x][y] = false;
}
}
else{
bool tmp=used[x][y];
used[x][y] = true;
n_dir = 3-dir;
nx = x + dx[n_dir];
ny = y + dy[n_dir];
DFS(nx, ny, n_dir);
used[x][y] = tmp;
// spin mirror
if(!used[x][y]){
used[x][y] = true;
arr[x][y] = '/';
n_dir = dir^1;
nx = x + dx[n_dir];
ny = y + dy[n_dir];
DFS(nx, ny, n_dir);
arr[x][y] = '\\';
used[x][y] = false;
}
}
}
}
int main(){
while(cin>>m>>n && (m!=-1 && n!=-1)){
if(out) cout<<"\n";
else out=true;
found=false;
start_x = start_y = end_x = end_y = -1;
for(int i=0 ; i<n ; i++){
for(int j=0 ; j<m ; j++){
used[i][j] = false;
cin>>arr[i][j];
if((i==0 || i==n-1 || j==0 || j==m-1) && arr[i][j]=='.'){
if(start_x == -1){
start_x = i;
start_y = j;
if(i==0) start_dir = 2;
else if(i==n-1) start_dir = 0;
else if(j==0) start_dir = 1;
else start_dir = 3;
}
else{
end_x = i;
end_y = j;
}
}
}
}
DFS(start_x, start_y, start_dir);
}
return 0;
}
```
### 時間複雜度分析
每筆輸入時間複雜度為 $O(nm)$
DFS 每層最多有 $2$ 種選擇，最多有 $nm$ 層
DFS 時間複雜度為 $O(2^{nm})$
每筆測資總時間複雜度為 $O(nm + 2^{nm})$
# UVa 291
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?291
如下圖所示，有編號 $1$~$5$ 的五個點，假設每一條邊都是雙向的
列出所有從 $1$ 開始每條邊最多只經過一次，並且每個點都有走到的情況，也就是一筆劃問題
## 想法 By Koios
要枚舉有哪些情況，就必須要先知道每個點可以連接到哪些點
我們可以預處理一張表，紀錄 $a$ 到 $b$ 是否有邊連通
接下來要符合一條邊的情況，就必須記錄每條邊是否被走過
一樣的，可以用一個表格紀錄 $a$ 到 $b$ 之間的邊是否被走過
最後就從 $1$ 點開始對於每個可以走的點都走過一次，枚舉出所有情況即可
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
bool nxt[6][6];
int res[10], vis[6][6];
void DFS(int depth, int last){
if(depth == 9){
for(int i=0 ; i<9 ; i++){
cout<<res[i];
}
cout<<"\n";
return;
}
for(int i=1 ; i<=6 ; i++){
// 確認 last 到 i 之間的邊是否走過
if(!vis[last][i] && !vis[i][last] && nxt[last][i]){
vis[last][i] = vis[i][last] = true;
res[depth] = i;
DFS(depth+1, i);
vis[last][i] = vis[i][last] = false;
}
}
}
int main(){
for(int i=0 ; i<6 ; i++){
for(int j=0 ; j<6 ; j++){
if(i==0) nxt[i][j] = true;
else nxt[i][j] = false;
vis[i][j] = false;
}
}
// 建立兩個點之間是否有邊的表
nxt[1][2] = nxt[1][3] = nxt[1][5] = true;
nxt[2][1] = nxt[2][3] = nxt[2][5] = true;
nxt[3][1] = nxt[3][2] = nxt[3][4] = nxt[3][5] = true;
nxt[4][3] = nxt[4][5] = true;
nxt[5][1] = nxt[5][2] = nxt[5][3] = nxt[5][4] = true;
res[0]=1;
DFS(1, 1);
return 0;
}
```
### 時間複雜度分析
DFS 每層最多 $4$ 種選擇，總共有 $8$ 層，時間複雜度為 $O(4^8)$
# UVa 399
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?399
有一張由 $d \times d$ 塊 $w \times h$ 大小的拼圖，每一塊拼圖的 上、左、下、右 都分別有一個數字
當兩塊拼圖之間的數字只差一個負號的時候(例如: `5` 和 `-5`)這兩塊拼圖就可以放在一起
此外，在四周的拼圖邊上數字都必須是 $0$
舉例來說，我們有這些拼圖
那麼可行的拼法為
## 想法 By Koios
因為拼圖有許多拼法，也許兩塊可以組合在一起，但是卻無法拼成完整的拼圖，因此可以考慮窮舉每個當前可行的情況，如果一直拚到最後一塊也沒問題，那就找到答案了
從左至右，從上至下枚舉每一個空格可以放哪些拼圖，檢查邊界、四周的拼圖
除了輸入和判斷比較繁複以外，基本都和 DFS 是相同的概念
### 程式碼
```cpp=
//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}}}))$
# UVa 598
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?598
給有一群字串，輸出這群字串的所有組合
## 想法 By Koios
這題跟問數字 $1$~$n$ 的所有組合是相同的問題，只是從數字變成字串而已，但是概念相同
因為求的是組合，所以過去出現過的組合就不能再以不同排列出現
也就是說要是我們已經枚舉過包含元素 $A$ 的所有組合，那下次元素 $A$ 就必定不能再使用
所以可以用一個變數 $start$ 紀錄上次最後用到哪個元素，下次枚舉就從 $start+1$ 開始即可
這題麻煩的是輸入有些複雜，可以使用 `stringstream` 處理輸入是 `a` 或是 `a b` 的情況
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
#include<sstream>
using namespace std;
int m, a, b, R, res[20];
string op, s, arr[20];
bool used[20];
void DFS(int depth, int start, int end){
if(depth == end){
for(int i=0 ; i<end ; i++){
if(i) cout<<", ";
cout<<arr[res[i]];
}
cout<<"\n";
return;
}
for(int i=start ; i<R ; i++){
res[depth]=i;
DFS(depth+1, i+1, end);
}
}
int main(){
// 輸入
cin>>m;
while(getchar() != '\n');
while(getchar() != '\n');
for(int t=0 ; t<m ; t++){
if(t) cout<<"\n";
R = 0;
getline(cin, op);
while(getline(cin, s) && s[0]!='\0'){
arr[R] = s;
R++;
}
// 判斷所求是哪種
if(op[0] == '*'){
a=1, b=R+1;
}
else{
stringstream ss;
ss<<op;
ss>>a;
ss>>b;
// 判斷有沒有 b
if(ss.fail()){
b=a+1;
}
else{
b++;
}
}
for(int i=a ; i<b ; i++){
if(i>a) cout<<"\n";
cout<<"Size "<<i<<"\n";
DFS(0, 0, i);
}
cout<<"\n";
}
return 0;
}
```
# UVa 639
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?639
給一個最多為 $4 \times 4$ 的西洋棋棋盤盤面，求最多能放上多少城堡，使得城堡之間不會互相攻擊到
盤面上可能會有牆壁，有牆壁的阻隔就不會互相攻擊到
## 想法 By Koios
枚舉每個空格是否要放城堡，找出城堡數量最多的
對於每個空格都可以選擇放與不放，如果要放則需要先檢查當前的盤面是否會衝突
如此一來就可以找到最大值
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int n;
char arr[5][5]; // . 表示空格 ; * 表示城堡 ; X 表示牆壁
bool feasible(int x, int y){
//above
for(int i=x-1 ; i>=0 ; i--){
if(arr[i][y] == 'X') break;
else if(arr[i][y] == '*') return false;
}
//left
for(int i=y-1 ; i>=0 ; i--){
if(arr[x][i] == 'X') break;
else if(arr[x][i] == '*') return false;
}
//below
for(int i=x+1 ; i<n ; i++){
if(arr[i][y] == 'X') break;
else if(arr[i][y] == '*') return false;
}
//right
for(int i=y+1 ; i<n ; i++){
if(arr[x][i] == 'X') break;
else if(arr[x][i] == '*') return false;
}
return true;
}
int DFS(int x, int y){
if(x == n || y == n){
return 0;
}
if(arr[x][y] == '.'){
if(feasible(x, y)){
int Max=0;
// 放城堡
arr[x][y] = '*';
if(y == n-1){
Max = 1+DFS(x+1, 0);
}
else{
Max = 1+DFS(x, y+1);
}
// 不放城堡
arr[x][y] = '.';
if(y == n-1){
Max = max(Max, DFS(x+1, 0));
}
else{
Max = max(Max, DFS(x, y+1));
}
return Max;
}
}
if(y == n-1){
return DFS(x+1, 0);
}
else{
return DFS(x, y+1);
}
}
int main(){
while(cin>>n && n){
for(int i=0 ; i<n ; i++){
for(int j=0 ; j<n ; j++){
cin>>arr[i][j];
}
}
cout<<DFS(0, 0)<<"\n";
}
return 0;
}
```
### 時間複雜度分析
輸入時間複雜度為 $O(n^2)$
DFS 每層最多有 $2$ 種選擇，共 $n^2$ 層
DFS 時間複雜度為 $O(2^{n^2})$
總時間複雜度為 $O(n^2 + 2^{n^2})$
# UVa 989
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?989
跟數獨問題相同，不過這次的版面大小可以從 $1 \times 1$ 到 $3 \times 3$
## 想法 By Koios
記錄小正方形、行、列每個數字是否出現過，透過 DFS 枚舉每種可能
### 程式碼
```cpp=
//By Koios1143
#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}}})$
###### tags: `SCIST 演算法 題解`
Sign in with Wallet
Connect another wallet