---
# System prepended metadata

title: 演算法課程題解 - DFS
tags: [SCIST 演算法 題解]

---

# 演算法課程題解 - 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
既然題目給的是兩兩之間的關係，那麼就可以想到用一個圖來表示
例如題目的第一筆測資

![](https://i.imgur.com/jxqzSfj.png)

那麼該怎麼枚舉呢?隨便選一個點走下去嗎?
從上圖可以發現到，因為 $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$ 開始每條邊最多只經過一次，並且每個點都有走到的情況，也就是一筆劃問題
![](https://i.imgur.com/6aqms5F.png)

## 想法 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$

舉例來說，我們有這些拼圖
![](https://i.imgur.com/JMa4VJj.png)

那麼可行的拼法為
![](https://i.imgur.com/khq6BXR.png)



## 想法 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 演算法 題解`