---
# System prepended metadata

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

---

# 演算法課程題解 - BFS

# TOJ 432
## 題目
https://toj.tfcis.org/oj/pro/432/

有一個 $N \times M$ 的棋盤，在這個棋盤上有 $F$ 個著火的點 $(x_i, y_i)$ 以及一個門 $(u, v)$
現在有個人在 $(x_{me}, y_{me})$ 的位置，每次可以上下左右選擇一個移動一格，請問這個人是否能在不碰到火的情況下走到門的位置

## 想法 By Koios
我們可以嘗試從人所在的位置開始，每次走一步，每一個方向都走過，直到找到門或是把全部可行的格子走過，那麼就會知道答案了

### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int n, m, f, arr[1005][1005], que[1000005][2];
int start_x, start_y, end_x, end_y, cur_x, cur_y, nx, ny;
bool vis[1005][1005], ans=false;

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

void BFS(){
	que[0][0] = start_x;
	que[0][1] = start_y;
	
	vis[start_x][start_y] = true;
	
	for(int i=0, j=1 ; i<j ; i++){
		cur_x = que[i][0];
		cur_y = que[i][1];
		// 找到門了
		if(cur_x == end_x && cur_y == end_y){
			ans=true;
			break;
		}
		// 四個方向都走過
		for(int k=0 ; k<4 ; k++){
			nx = cur_x + dx[k];
			ny = cur_y + dy[k];
			// 把超出棋盤的移除
			if(nx > n || nx <= 0 || ny <= 0 || ny > m) continue;
			if(!vis[nx][ny] && arr[nx][ny] != 1){
				vis[nx][ny] = true;
				que[j][0] = nx;
				que[j][1] = ny;
				j++;
			}
		}
	}
}

int main(){
	cin>>n>>m;
	for(int i=1 ; i<=n ; i++){
		for(int j=1 ; j<=m ; j++){
			arr[i][j] = 0;
			vis[i][j] = false;
		}
	}
	cin>>start_x>>start_y>>end_x>>end_y;
	cin>>f;
	for(int i=0, x, y ; i<f ; i++){
		cin>>x>>y;
		arr[x][y] = 1;
	}
	BFS();
	if(ans){
		cout<<"Cool!\n";
	}
	else{
		cout<<"Harakiri!\n";
	}

	return 0;
}
```

### 時間複雜度分析
輸入時間複雜度為 $O(nm + f)$
BFS 時間複雜度為 狀態數 $\times$ 操作數量 $= (nm) \times 4$，計為 $O(nm)$
總時間複雜度為 $O(2nm + f)$

# UVa 439
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?439

在一個 $8 \times 8$ 的西洋棋棋盤上有一個騎士，給定騎士當前的位置，求到達某個指定的位置所需的最少步數，保證必定有解
因為是騎士，所以當然要用騎士的走法

## 想法 By Koios
因為要找的是最少的步數，所以可以想到用 BFS 來搜尋
每次將每種走法都走一步，直到走到詢問的點

### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int que[1010][2], dis[10][10], ans;
int start_x, start_y, end_x, end_y, cur_x, cur_y, nx, ny;
int dx[] = {-2, -2, -1, -1, 1, 1, 2, 2};
int dy[] = {-1, 1, -2, 2, -2, 2, -1, 1};
bool vis[10][10];
char Ax, Ay, Bx, By;

int BFS(){
	que[0][0] = start_x;
	que[0][1] = start_y;
	vis[start_x][start_y] = true;
	for(int i=0, j=1 ; i<j ; i++){
		cur_x = que[i][0];
		cur_y = que[i][1];
		if(cur_x == end_x && cur_y == end_y){
			return dis[end_x][end_y];
		}
		// 對於 8 個走法走一步
		for(int k=0 ; k<8 ; k++){
			nx = cur_x + dx[k];
			ny = cur_y + dy[k];
			// 移除超出棋盤的點
			if(nx <= 0 || nx > 8 || ny <= 0 || ny > 8) continue;
			if(!vis[nx][ny]){
				vis[nx][ny] = true;
				dis[nx][ny] = dis[cur_x][cur_y]+1;
				que[j][0] = nx;
				que[j][1] = ny;
				j++;
			}
		}
	}
	return -1;
}

int main(){
	while(cin>>Ay>>Ax>>By>>Bx){
		// 將棋盤座標轉換成平面座標
		start_x = Ax-'0';
		start_y = Ay-'a'+1;
		end_x = Bx-'0';
		end_y = By-'a'+1;
		
		for(int i=0 ; i<10 ; i++){
			for(int j=0 ; j<10 ; j++){
				dis[i][j] = 0;
				vis[i][j] = false;
			}
		}
		
		ans = BFS();
		cout<<"To get from "<<Ay<<Ax<<" to "<<By<<Bx<<" takes "<<ans<<" knight moves.\n";
	}

	return 0;
}
```

### 時間複雜度分析
令 $n = 8$
每筆測資輸入時間複雜度為 $O(1)$
每筆測資 BFS 時間複雜度為 狀態數 $\times$ 操作數量 $= (n^2) \times 8$，計為 $O(n^2)$
每筆測資總時間複雜度為 $O(n^2)$

# UVa 532
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?532

有一個三維的地牢，包含了 `#` `.` `S` `E` ，分別表示 障礙物、空格、起點、終點
每次移動可以選擇 前、後、左、右、上、下 六種走法
求從起點走到終點的最短步數，如果無解則輸出 `Trapped!`

## 想法 By Koios
因為要找的是最小步數，所以可以想到用 BFS 來搜尋，只是這次變成三維而已

### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int L, R, C, ans;
int dx[6] = {1, -1, 0, 0, 0, 0};
int dy[6] = {0, 0, 1, -1, 0, 0};
int dz[6] = {0, 0, 0, 0, 1, -1};
char arr[35][35][35];
bool vis[35][35][35];

struct dot{
	int x, y, z;
	int dis;
	// 建立一個 dot 元素，並且給定 x y z
	dot(int X, int Y, int Z):x{X}, y{Y}, z{Z}, dis{0} {}
	// 建立一個空 dot
	dot(): x{-1}, y{-1}, z{-1}, dis{0} {}
};

dot start, End, cur, nxt;

int BFS(){
	dot que[50000];
	que[0] = start;
	vis[start.x][start.y][start.z] = true;
	
	for(int i=0, j=1 ; i<j ; i++){
		cur = que[i];
		if(cur.x == End.x && cur.y == End.y && cur.z == End.z){
			return cur.dis;
		}
		for(int k=0 ; k<6 ; k++){
			nxt = cur;
			nxt.x += dx[k];
			nxt.y += dy[k];
			nxt.z += dz[k];
			
			// 超出界線
			if(nxt.x < 0 || nxt.x >= L || nxt.y < 0 || nxt.y >= R || nxt.z < 0 || nxt.z >= C) continue;
			if(!vis[nxt.x][nxt.y][nxt.z] && arr[nxt.x][nxt.y][nxt.z] != '#'){
				vis[nxt.x][nxt.y][nxt.z] = true;
				nxt.dis = cur.dis + 1;
				que[j] = nxt;
				j++;
			}
		}
	}
	return -1;
}

int main(){
	while(cin>>L>>R>>C && (L!=0 && R!=0 && C!=0)){
		for(int i=0 ; i<L ; i++){
			for(int j=0 ; j<R ; j++){
				for(int k=0 ; k<C ; k++){
					cin>>arr[i][j][k];
					vis[i][j][k] = false;
					if(arr[i][j][k] == 'S'){
						start = dot(i, j, k);
					}
					else if(arr[i][j][k] == 'E'){
						End = dot(i, j, k);
					}
				}
			}
		}
		ans = BFS();
		if(ans == -1){
			cout<<"Trapped!\n";
		}
		else{
			cout<<"Escaped in "<<ans<<" minute(s).\n";
		}
	}

	return 0;
}
```

### 時間複雜度分析
每筆測資輸入時間複雜度為 $O(LRC)$
每筆測資 BFS 時間複雜度為 狀態數 $\times$ 操作數量 $= (LRC) \times 6$，計為 $O(LRC)$
每筆測資 總時間複雜度為 $O(LRC)$

# UVa 10102
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?10102

有一個 $M \times M$ 的棋盤，棋盤上有許多 `1` `2` `3`
請問所有以 `1` 為起點 `3` 為終點的最短路徑當中的最長長度為何，並且保證必定有解

## 想法 By Koios
因為要找最短路徑，所以可以想到用 BFS 來搜尋
不過因為要求的是全部的路徑中的最長，所以可以每次選擇其中一個 `1` 當作起點計算最短路徑，然後取出最大值

### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int m, R, ans, res, que[10005][2], dis[105][105], start[10005][2];
int cur_x, cur_y, nx, ny;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
char arr[105][105];
bool vis[105][105];

int BFS(int n){
	que[0][0] = start[n][0];
	que[0][1] = start[n][1];
	vis[start[n][0]][start[n][1]] = true;
	dis[start[n][0]][start[n][1]] = 0;
	
	for(int i=0, j=1 ; i<j ; i++){
		cur_x = que[i][0];
		cur_y = que[i][1];
		if(arr[cur_x][cur_y] == '3'){
			return dis[cur_x][cur_y];
		}
		for(int k=0 ; k<4 ; k++){
			nx = cur_x + dx[k];
			ny = cur_y + dy[k];
			if(nx < 0 || nx >= m || ny < 0 || ny >= m) continue;
			if(!vis[nx][ny]){
				vis[nx][ny] = true;
				dis[nx][ny] = dis[cur_x][cur_y] + 1;
				que[j][0] = nx;
				que[j][1] = ny;
				j++;
			}
		}
	}
	return 0;
}

int main(){
	while(cin>>m){
		ans=res=0;
		R=0;
		for(int i=0 ; i<m ; i++){
			for(int j=0 ; j<m ; j++){
				cin>>arr[i][j];
				if(arr[i][j] == '1'){
					start[R][0] = i;
					start[R][1] = j;
					R++;
				}
			}
		}
		for(int i=0 ; i<R ; i++){
			for(int j=0 ; j<105 ; j++){
				for(int k=0 ; k<105 ; k++){
					vis[j][k] = false;
				}
			}
			res = BFS(i);
			ans = max(ans, res);
		}
		cout<<ans<<"\n";
	}
	return 0;
}
```

### 時間複雜度分析
每筆測資輸入時間複雜度為 $O(m^2)$
每筆測資 BFS 時間複雜度為 狀態數 $\times$ 操作數量 $= m^2 \times 4$，每次要做 $R$ 次操作，計為 $O(Rm^2)$
每筆測資總時間複雜度為 $O(Rm^2)$

# UVa 10959
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?10959

我們可以把 Don Giovanni 當作是所有人的起點
所有跟 Don Giovanni 跳過舞的人都距離 Don Giovanni $1$
所有跟距離 Don Giovanni $n$ 的人跳過舞，則他的距離會變成 $n+1$

現在告訴你有 $P$ 個人，並且有 $D$ 對跳舞的人，求每個人到 Don Giovanni 的距離

## 想法 By Koios
可以把所有跳舞的人之間連上一條邊
然後從 Don Giovanni $(0)$ 開始，把所有邊都走過一遍
因為要的是距離，可以用 BFS ，如此一來第一次走到的距離就是 $1$，第二次距離就是 $2$，以此類推

### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int t, P, D, que[1005], dis[1005], cur;
bool edge[1005][1005];

void BFS(){
	que[0] = 0;
	dis[0] = 0;
	for(int i=0, j=1 ; i<j ; i++){
		cur = que[i];
		for(int nxt=0 ; nxt<P ; nxt++){
			if(edge[cur][nxt] && dis[nxt] > dis[cur] + 1){
				dis[nxt] = dis[cur] + 1;
				que[j] = nxt;
				j++;
			}
		}
	}
}

int main(){
	cin>>t;
	for(int i=0 ; i<t ; i++){
		if(i) cout<<"\n";
		for(int j=0 ; j<1005 ; j++){
			// 先假設每個點愈離都是一個極大值
			dis[j] = 1e9+10;
			for(int k=0 ; k<1005 ; k++){
				edge[j][k] = false;
			}
		}
		cin>>P>>D;
		for(int j=0, a, b ; j<D ; j++){
			cin>>a>>b;
			edge[a][b] = edge[b][a] = true;
		}
		BFS();
		for(int i=1 ; i<P ; i++){
			cout<<dis[i]<<"\n";
		}
	}

	return 0;
}
```

### 時間複雜度分析
每筆測資輸入時間複雜度為 $O(D)$
每筆測資 BFS 時間複雜度為 $O(P)$
總時間複雜度為 $O(t(D + P))$

# UVa 11352
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?11352

在一個 $M \times N$ 的西洋棋棋盤上有一些騎士以及兩個王國 $A, B$
現在有一個國王要從王國 $A$ 走到王國 $B$，求最短路徑，若無解則輸出 `King Peter, you can’t go now!`

## 想法 By Koios
因為要求的是最短路徑，所以可以想到用 BFS 來求解

### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int t, m, n, ans, que[100005][2], dis[105][105];
// 騎士的走法
int H_dx[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
int H_dy[8] = {-1, 1, -2, 2, -2, 2, -1, 1};
// 國王的走法
int K_dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int K_dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

int start_x, start_y, end_x, end_y, cur_x, cur_y, nx, ny;
char arr[105][105], tmp;
bool vis[105][105];

int BFS(){
	que[0][0] = start_x;
	que[0][1] = start_y;
	dis[start_x][start_y] = 0;
	vis[start_x][start_y] = true;
	
	for(int i=0, j=1 ; i<j ; i++){
		cur_x = que[i][0];
		cur_y = que[i][1];
		if(cur_x == end_x && cur_y == end_y){
			return dis[end_x][end_y];
		}
		for(int k=0 ; k<8 ; k++){
			nx = cur_x + K_dx[k];
			ny = cur_y + K_dy[k];
			if(nx < 0 || nx >=m || ny < 0 || ny >= n) continue;
			if(!vis[nx][ny] && arr[nx][ny] != '#'){
				vis[nx][ny] = true;
				dis[nx][ny] = dis[cur_x][cur_y] + 1;
				que[j][0] = nx;
				que[j][1] = ny;
				j++;
			}
		}
	}
	return -1;
}

int main(){
	cin>>t;
	while(t--){
		cin>>m>>n;
		// 初始化
		for(int i=0 ; i<m ; i++){
			for(int j=0 ; j<n ; j++){
				arr[i][j] = '.';
				vis[i][j] = false;
			}
		}
		
		for(int i=0 ; i<m ; i++){
			for(int j=0 ; j<n ; j++){
				cin>>tmp;
				if(tmp == 'A'){
					arr[i][j] = tmp;
					start_x = i;
					start_y = j;
				}
				else if(tmp == 'B'){
					arr[i][j] = tmp;
					end_x = i;
					end_y = j;
				}
				else if(tmp == 'Z'){
					arr[i][j] = '#';
					for(int k=0 ; k<8 ; k++){
						nx = i + H_dx[k];
						ny = j + H_dy[k];
						if(nx >= 0 && nx < m && ny >= 0 && ny < n && arr[nx][ny] == '.'){
							arr[nx][ny] = '#';
						}
					}
				}
			}
		}
		
		ans = BFS();
		if(ans == -1){
			cout<<"King Peter, you can't go now!\n";
		}
		else{
			cout<<"Minimal possible length of a trip is "<<ans<<"\n";
		}
	}

	return 0;
}
```

### 時間複雜度分析
每筆測資輸入時間複雜度為 $O(nm)$
每筆測資 BFS 時間複雜度為 狀態數 $\times$ 操作數量 $= (nm) \times 8$，計為 $O(nm)$
總時間複雜度為 $O(t(nm))$

# UVa 11730
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?11730

給兩個數字 $S, T$
數字 $A$ 可以透過加上 $A$ 除了本身以外的質因數轉移成 $A'$
問最少透過多少次轉移從 $S$ 變成 $T$，若無解則輸出 $-1$

## 想法 By Koios
因為要找的是最少的步數，所以可以想到用 BFS 來搜尋答案
不過如果每次都要重新尋找質因數會消耗太多時間
所以可以預先建立質數表，每次只需要尋找這些質數是否符合條件即可

### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int s, t, px, cur, Case=1, prime[1005], que[1000000], dis[1005];
bool not_prime[1005], vis[1005];

void build(){
	for(int i=0 ; i<=1000 ; i++){
		not_prime[i] = false;
	}
	int i;
	px=1;
	prime[0] = 2;
	for(i=3 ; i*i<=1000 ; i+=2){
		if(!not_prime[i]){
			prime[px++] = i;
			for(int j=i*i ; j<=1000 ; j+=2*i){
				not_prime[j] = true;
			}
		}
	}
	for( ; i<=1000 ; i+=2){
		if(!not_prime[i]){
			prime[px++] = i;
		}
	}
}

int BFS(int start, int end){
	que[0] = start;
	vis[start] = true;
	for(int i=0, j=1 ; i<j ; i++){
		cur = que[i];
		if(cur == end){
			return dis[end];
		}
		for(int k=0 ; k<px && prime[k]<cur && cur+prime[k]<=end ; k++){
			if(cur%prime[k] == 0 && !vis[cur + prime[k]]){
				que[j++] = cur + prime[k];
				vis[cur + prime[k]] = true;
				dis[cur + prime[k]] = dis[cur] + 1;
			}
		}
	}
	return -1;
}

int main(){
	// 建立質數表
	build();
	while(cin>>s>>t && (s!=0 && t!=0)){
		for(int i=0 ; i<=1000 ; i++) dis[i] = 0, vis[i] = false;
		cout<<"Case "<<Case++<<": "<<BFS(s, t)<<"\n";
	}
	return 0;
}
```

# Kattis Conquest Campaign
## 題目
https://open.kattis.com/problems/conquestcampaign

給一張 $R \times C$ 的地圖，其中有 $N$ 個可重複的點，標示我們的起點
圖上沒有任何障礙物，在這至多 $N$ 個起點每天我們可以往 上下左右 四個方向擴散，請問最少幾天可以把全部地圖佔領

## 想法 By Koios
因為要球最少步驟，所以想到用 BFS 來實作
會影響到未來發展的只有我們佔據了哪些點，所以狀態只需要紀錄被佔領的點座標即可
接下來每次向外四個方向擴散

要注意的是，起點可能重複給，但是實際上重複是沒有意義的
並且為了方便確定當前是不是全部的點都佔領了，我們透過確認當前總共有多少座標被標記在 BFS 的序列當中，那麼重複的點就不應該被重複計算，所以要先拔除

### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int R, C, N, S, que[10005][2], dis[105][105];
int dx[] = {-1, 0, 0, 1};
int dy[] = {0, -1, 1, 0};
bool vis[105][105];

void print_all(){
	for(int i=1 ; i<=R ; i++){
		for(int j=1 ; j<=C ; j++){
			if(vis[i][j]) cout<<"*";
			else cout<<'.';
		}
		cout<<"\n";
	}
	cout<<"\n";
}

int BFS(){
	for(int i=0, j=S, x, y, nx, ny ; i<j ; i++){
		x = que[i][0];
		y = que[i][1];
		if(j == R*C){
			// 檢查是否已經佔領所有點
			return dis[que[j-1][0]][que[j-1][1]];
		}
		for(int k=0 ; k<4 ; k++){
			nx = x + dx[k];
			ny = y + dy[k];
			if(nx <= 0 || nx > R || ny <= 0 || ny > C) continue;
			if(!vis[nx][ny]){
				vis[nx][ny] = true;
				dis[nx][ny] = dis[x][y] + 1;
				que[j][0] = nx;
				que[j][1] = ny;
				j++;
			}
		}
	}
	return -1;
}

int main(){
	for(int i=0 ; i<105 ; i++){
		for(int j=0 ; j<105 ; j++){
			vis[i][j] = false;
		}
	}
	cin>>R>>C>>N;
	S=0; // 紀錄不重複的起點數量
	for(int i=0, x, y ; i<N ; i++){
		cin>>x>>y;
		if(!vis[x][y]){
			que[S][0] = x;
			que[S][1] = y;
			vis[x][y] = true;
			dis[x][y] = 1;
			S++;
		}
	}
	cout<<BFS()<<"\n";
	return 0;
}
```

### 時間複雜度分析
輸入時間複雜度為 $O(N)$
BFS 時間複雜度為 狀態數 $\times$ 操作的數量 $= (nm) \times 4$ ，計為 $O(nm)$
總時間複雜度為 $O(N + nm)$

# UVa 571
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?571

倒水問題，給兩個容量分別為 $A, B$ 加侖的桶子，有 $6$ 種操作
- fill A
- fill B
- empty A
- empty B
- pour A B
- pour B A

請問最少要花多少步驟可以組合出 $N$ 加侖的水

## 想法 By Koios
因為要問的是最小的步驟，所以可以想到用 BFS 來搜尋解法
每次檢查六種操作是否可以執行，然後枚舉出所有的操作，直到組合出 $N$ 加侖的水

### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int a, b, max_a, max_b, cur_a, cur_b, n, ans;
string methods[] = {"fill A", "fill B", "empty A", "empty B", "pour A B", "pour B A"};
/*
methods:
0: fill A
1: fill B
2: empty A
3: empty B
4: pour A B
5: pour B A
*/
/*
0: cur_a
1: cur_b
2: 從哪個點來的
3: 用的方法編號
*/
int res[1000005], que[1005][4];
bool vis[1005][1005];

void BFS(){
	que[0][0] = 0;
	que[0][1] = 0;
	que[0][2] = -1;
	que[0][3] = -1;
	vis[0][0] = true;
	
	for(int i=0, j=1 ; i<j ; i++){
		cur_a = que[i][0];
		cur_b = que[i][1];
		if(cur_a == n || cur_b == n){
			ans = i;
			return;
		}
		
		if(cur_a != max_a && !vis[max_a][cur_b]){
			// fill A
			vis[max_a][cur_b] = true;
			que[j][0] = max_a;
			que[j][1] = cur_b;
			que[j][2] = i;
			que[j][3] = 0;
			j++;
		}
		if(cur_b != max_b && !vis[cur_a][max_b]){
			// fill B
			vis[cur_a][max_b] = true;
			que[j][0] = cur_a;
			que[j][1] = max_b;
			que[j][2] = i;
			que[j][3] = 1;
			j++;
		}
		if(cur_a != 0 && !vis[0][cur_b]){
			// empty A
			vis[0][cur_b] = true;
			que[j][0] = 0;
			que[j][1] = cur_b;
			que[j][2] = i;
			que[j][3] = 2;
			j++;
		}
		if(cur_b != 0 && !vis[cur_a][0]){
			// empty B
			vis[cur_a][0] = true;
			que[j][0] = cur_a;
			que[j][1] = 0;
			que[j][2] = i;
			que[j][3] = 3;
			j++;
		}
		if(max_b-cur_b >= cur_a){
			// pour A B
			if(!vis[0][cur_b+cur_a]){
				vis[0][cur_b+cur_a] = true;
				que[j][0] = 0;
				que[j][1] = cur_b+cur_a;
				que[j][2] = i;
				que[j][3] = 4;
				j++;
			}
		}
		else{
			if(!vis[cur_a-(max_b-cur_b)][max_b]){
				vis[cur_a-(max_b-cur_b)][max_b] = true;
				que[j][0] = cur_a-(max_b-cur_b);
				que[j][1] = max_b;
				que[j][2] = i;
				que[j][3] = 4;
				j++;
			}
		}
		if(max_a-cur_a >= cur_b){
			// pour B A
			if(!vis[cur_a+cur_b][0]){
				vis[cur_a+cur_b][0] = true;
				que[j][0] = cur_a+cur_b;
				que[j][1] = 0;
				que[j][2] = i;
				que[j][3] = 5;
				j++;
			}
		}
		else{
			if(!vis[max_a][cur_b-(max_a-cur_a)]){
				vis[max_a][cur_b-(max_a-cur_a)] = true;
				que[j][0] = max_a;
				que[j][1] = cur_b-(max_a-cur_a);
				que[j][2] = i;
				que[j][3] = 5;
				j++;
			}
		}
	}
}

// 利用遞迴的方式輸出過程
void print_ans(int cur){
	if(que[cur][2] == -1){
		return;
	}
	print_ans(que[cur][2]);
	cout<<methods[que[cur][3]]<<"\n";
}

int main(){
	while(cin>>max_a>>max_b>>n){
		ans=-1;
		for(int i=0 ; i<1005 ; i++){
			for(int j=0 ; j<1005 ; j++){
				vis[i][j] = 0;
			}
		}
		BFS();
		print_ans(ans);
		cout<<"success\n";
	}
	return 0;
}
```

# UVa 10047
## 題解
http://domen111.github.io/UVa-Easy-Viewer/?10047

有一個輪子，從圓心將輪子平分成五等分，每等分都是 $72^{\circ}$，並且都有一個顏色，如附圖

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

一開始這個輪子都是以**綠色**觸碰地面
在一張地圖上有起點、終點、障礙物，現在輪子在起點朝向北方，每次你可以選擇要 **前進**、**右轉$90^{\circ}$**、**左轉$90^{\circ}$**
每次前進，輪子就會以下一個顏色觸碰地面
請問，走到終點並且以綠色觸碰地面的最少操作數是多少

## 想法 By Koios
因為要找的是最少操作數，可以想到用 BFS
因為除了走到終點以外，還需要符合綠色觸碰地面的條件，所以我們可以以 不同的方向、不同顏色觸碰地面 去走過走過的點
所以對於每個點的狀態有

- X 座標
- Y 座標
- 方向
- 顏色

接下來分別對三個不的同操作來轉移，記錄下 操作次數、拜訪與否 即可

這題跟過去 BFS 不太一樣的是，之前的題目大概都是只拿座標當作狀態，但是在本題多了方向、顏色的因素
計算操作次數也是一樣，如果只拿座標去當作參數，那會造成不同的狀態共用一個操作次數，這樣是不合理的
我自己寫這題的時候就沒考慮到這些，然後被卡了很久w

### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
// 0: N, 1: W, 2: S, 3: E
// 0: Green, 1: Black, 2: Red, 3: Blue, 4: White
int n, m, x, y, start_x, start_y, end_x, end_y, dir, color, nx, ny, ncolor, ndir, ans, Case=1;
int dis[30][30][4][5], que[2000000][4];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};
int co[] = {1, 0, 0};
int dd[] = {0, 1, 3};
const int MaxN = 2147483647;
char arr[30][30];
bool vis[30][30][4][5];

int BFS(){
	que[0][0] = start_x;
	que[0][1] = start_y;
	que[0][2] = 0;
	que[0][3] = 0;
	vis[start_x][start_y][0][0] = true;
	dis[start_x][start_y][0][0] = 0;
	
	for(int i=0, j=1 ; i<j ; i++){
		x = que[i][0];
		y = que[i][1];
		dir = que[i][2];
		color = que[i][3];
		if(arr[x][y] == 'T' && color == 0){
			return dis[x][y][dir][color];
		}
		for(int k=0 ; k<3 ; k++){
			nx = x + co[k] * dx[dir];
			ny = y + co[k] * dy[dir];
			ndir = (dir + dd[k])%4;
			ncolor = (color+co[k])%5;
			if(nx<0 || nx>=n || ny<0 || ny>=m || arr[nx][ny] == '#') continue;
			if(!vis[nx][ny][ndir][ncolor]){
				vis[nx][ny][ndir][ncolor] = true;
				dis[nx][ny][ndir][ncolor] = dis[x][y][dir][color] + 1;
				que[j][0] = nx;
				que[j][1] = ny;
				que[j][2] = ndir;
				que[j][3] = ncolor;
				j++;
			}
		}
	}
	return -1;
}

int main(){
	while(cin>>n>>m && (n!=0 && m!=0)){
		if(Case>1) cout<<"\n";
		for(int i=0 ; i<n ; i++){
			for(int j=0 ; j<m ; j++){
				for(int k=0 ; k<4 ; k++){
					for(int l=0 ; l<5 ; l++){
						vis[i][j][k][l] = false;
						dis[i][j][k][l] = MaxN;
					}
				}
				cin>>arr[i][j];
				if(arr[i][j] == 'S'){
					start_x=i;
					start_y=j;
				}
				else if(arr[i][j] == 'T'){
					end_x = i;
					end_y = j;
				}
			}
		}
		ans = BFS();
		if(ans != -1){
			cout<<"Case #"<<Case++<<"\n"<<"minimum time = "<<ans<<" sec\n";
		}
		else{
			cout<<"Case #"<<Case++<<"\n"<<"destination not reachable\n";
		}
	}

	return 0;
}
```

### 時間複雜度分析
每筆測資輸入時間複雜度為 $O(nm)$
每筆測資 BFS 時間複雜度為 狀態數 $\times$ 操作的數量 $= 20nm \times 3$，大約是 $O(nm)$
每筆測資總時間複雜度約為 $O(nm)$

# UVa 321
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?321

在一個房子裡面有 $r$ 個房間、 $d$ 個通道以及 $s$ 個電燈開關
告訴你這 $d$ 個通道分別連接哪兩個房間，以及這 $s$ 個電燈開關位在哪個房間，分別可以控制哪個房間的電燈

現在有個人在編號 $1$ 的房間當中，想要走到編號 $r$ 的房間，並且由於他怕黑，經過的房間必定要是有開燈的才可以進入

每次可以選擇要觸發在當前房間有的開關，或是要走到下一個房間
編號 $1$ 的房間燈一開始是開的狀態，請問最少需要多少的操作可以走到編號 $r$ 的房間，並且輸出其過程

## 想法 By Koios
因為要找的是最少的操作數，所以可以想到用 BFS 來解

題目要求當前所在房間的燈要是開的，所以當前在哪個房間是重要的狀態
並且當前有哪些燈是開著的也會影響到未來的發展
所以對於這一題有兩個狀態 **所在房間編號** 以及 **所有房間燈的狀態**

至於轉移則有兩種方式
第一種是移動到有連接的房間，需要保證下個房間燈是開的
第二種是切換某個房間的電燈開關，需要確保不會關到自己的燈

有了狀態以及轉移，接下來只要確保每次轉移的狀態過去都沒有出現過即可

這一題我用數字的每個 bit 去記錄 **房間燈開關的狀態** 以及 **房間 x 可以操作哪個房間的電燈**
轉移當中的切換開關就可以使用位元運算去找到下一個可行的點(詳細看程式碼)

至於回朔的方式，這一題我是用遞迴
在 BFS 轉移的過程當中去紀錄 **從誰轉移過來**
因為我是用陣列去模擬 queue ，所以資料都會留著，就可以直接紀錄是從陣列的哪個 index 轉移過來即可

至於要判斷是哪個操作，我們可以觀察 **房間燈開關的狀態**
如果前後狀態相同就是走到下一個房間
如果有個房間燈狀態從 $0 \to 1$，那就是開燈
反之就是關燈

### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int r, d, s, ans, Case=1, edge_len[15], io[15], edge[15][15];
int que_id[40000], que_light[40000], from[40000], room_id[3000];
bool vis[15][3000];

int BFS(){
	// 一開始的房間是在編號 1
	// 一開始房間 1 的燈是開的，所以 2^1 的位置要是 1
	que_id[0] = 1;
	que_light[0] = 2;
	vis[1][2] = true;
	
	for(int head=0, tail=1, id, light ; head<tail ; head++){
		id = que_id[head];
		light = que_light[head];
		
		// 找到答案要確保只有編號 r 的房間燈是亮的
		if(id == r && light == (1<<r)){
			return head;
		}
		
		// 走到下一個房間
		for(int i=0 ; i<edge_len[id] ; i++){
			if(!vis[edge[id][i]][light] && (light & (1<<edge[id][i])) > 0){
				que_id[tail] = edge[id][i];
				que_light[tail] = light;
				from[tail] = head;
				tail++;
			}
		}
		
		// 切換開關
		// i&=~lowbit 會讓 i 當中最低位的 1 變成 0，其他不變
		for(int i=io[id], lowbit, nxt_light ; i!=0 ; i&=~lowbit){
			lowbit = (i & -i); // 取得 i 最低位的位置
			nxt_light = light ^ lowbit; // 得到可以操作的開關
			// 切換前要先確認不會關到自己當前的房間燈
			if(!vis[id][nxt_light] && (nxt_light & (1<<id))!=0){
				vis[id][nxt_light] = true;
				que_id[tail] = id;
				que_light[tail] = nxt_light;
				from[tail] = head;
				tail++;
			}
		}
	}
	return -1;
}

void print_ans(int step, int cur_idx){
	if(from[cur_idx] == -1){
		cout<<"The problem can be solved in "<<step<<" steps:\n";
		return;
	}
	int pre_idx = from[cur_idx];
	print_ans(step+1, pre_idx);
	
	if(que_light[pre_idx] == que_light[cur_idx]){
		// 操作是走到下個房間
		cout<<"- Move to room "<<que_id[cur_idx]<<".\n";
	}
	else{
		// 操作是切換開關
		// 透過 xor 可以剩下被切換的房間是 1
		// 透過預先建好的表對應到房間 id
		// 也可以改用 log (以二為底)
		int room = room_id[que_light[cur_idx] ^ que_light[pre_idx]];
		if((que_light[cur_idx] & (1<<room)) == 0){
			// off
			cout<<"- Switch off light in room "<<room<<".\n";
		}
		else{
			// on
			cout<<"- Switch on light in room "<<room<<".\n";
		}
	}
}

int main(){
	for(int i=0 ; i<=10 ; i++){
		// 將燈的值轉換成房間 id
		room_id[1<<i] = i;
	}
	while(cin>>r>>d>>s && (r!=0 || d!=0 || s!=0)){
		// 初始化
		from[0] = -1;
		for(int i=0 ; i<15 ; i++){
			edge_len[i] = io[i] = 0;
			for(int j=0 ; j<3000 ; j++){
				vis[i][j] = false;
			}
		}
		
		// 將每條邊用類似 list 的方式儲存比較方便
		// 每條 list 的長度紀錄在 edge_len[]
		for(int i=0, a, b ; i<d ; i++){
			cin>>a>>b;
			edge[a][edge_len[a]++] = b;
			edge[b][edge_len[b]++] = a;
		}
		// 利用每個 bit 去記錄房間 a 的開關控制的房間
		for(int i=0, a, b ; i<s ; i++){
			cin>>a>>b;
			io[a] |= (1<<b);
		}
		
		ans = BFS();
		cout<<"Villa #"<<Case++<<"\n";
		if(ans == -1){
			cout<<"The problem cannot be solved.\n";
		}
		else{
			print_ans(0, ans);
		}
		cout<<"\n";
	}

	return 0;
}
```

### 時間複雜度分析
每筆測資輸入時間複雜度為 $O(d + s)$
每筆測資 BFS 時間複雜度為 狀態數 $\times$ 操作的數量 $(d \times 2^s) \times (s + d)$，大約是 $O(2^s)$
每筆測資遞迴求解時間複雜度為 $O(r)$
每筆測資總時間複雜度為 $O(2^s)$

# TOJ 449
## 題目
https://toj.tfcis.org/oj/pro/449/

給一張迷宮的地圖，其中包含障礙物、門、鑰匙、起點、終點
每個門都需要有相對應的鑰匙才可以打開，而一把鑰匙可以無限次使用
地圖可能有多終點
每次可以選擇上下左右一個方向前進，請問最少需要花多少的步驟走到終點

## 想法 By Koios
因為要找的是最少步驟，因此可以想到用 BFS 來解

現在所擁有的鑰匙會影響到未來發展，因此每次需要考慮到當前有哪些鑰匙
因此我們的狀態就包含了 **當前座標** 以及 **擁有的鑰匙**

我們依舊可以使用 bit 的方式去記錄每個鑰匙是否擁有
每次走到門就檢查該 bit 是否是 1

### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int n, m, ans, start_x, start_y;
int dx[] = {-1, 0, 0, 1};
int dy[] = {0, -1, 1, 0};
int key_num[26], dis[105][105][50];
int que[10010][3];
string keys="RGBY";
char arr[105][105];
bool vis[105][105][50];

int BFS(){
	que[0][0] = start_x;
	que[0][1] = start_y;
	que[0][2] = 0;
	dis[start_x][start_y][0] = 0;
	vis[start_x][start_y][0] = true;
	
	for(int head=0, tail=1, x, y, key, nx, ny, nkey ; head<tail ; head++){
		x = que[head][0];
		y = que[head][1];
		key = que[head][2];
		
		if(arr[x][y] == 'X'){
			return dis[x][y][key];
		}
		
		for(int i=0 ; i<4 ; i++){
			nx = x + dx[i];
			ny = y + dy[i];
			nkey = key;
			if(nx<0 || nx>=n || ny<0 || ny>=m || arr[nx][ny] == '#') continue;
			
			if(arr[nx][ny] == 'R' || arr[nx][ny] == 'G' || arr[nx][ny] == 'B' || arr[nx][ny] == 'Y'){
				// 下一個點是門，檢查該 bit 是否為 1
				if((key & (1<<key_num[arr[nx][ny]-'A'])) == 0){
					continue;
				}
			}
			else if(arr[nx][ny] == 'r' || arr[nx][ny] == 'g' || arr[nx][ny] == 'b' || arr[nx][ny] == 'y'){
				// 下個點是鑰匙，更新擁有的鑰匙
				nkey = (key | (1<<key_num[arr[nx][ny]-'a']));
			}
			if(!vis[nx][ny][nkey]){
				vis[nx][ny][nkey] = true;
				que[tail][0] = nx;
				que[tail][1] = ny;
				que[tail][2] = nkey;
				dis[nx][ny][nkey] = dis[x][y][key] + 1;
				tail++;
			}
		}
	}
	return -1;
}

int main(){
	// 把鑰匙對應一個數字
	for(int i=0 ; i<keys.size() ; i++){
		key_num[keys[i]-'A'] = i;
	}
	while(cin>>n>>m){
		for(int i=0 ; i<n ; i++){
			for(int j=0 ; j<m ; j++){
				for(int k=0 ; k<50 ; k++){
					vis[i][j][k] = false;
				}
				cin>>arr[i][j];
				if(arr[i][j] == '*'){
					start_x = i;
					start_y = j;
				}
			}
		}
		ans = BFS();
		if(ans == -1){
			cout<<"The poor student is trapped!\n";
		}
		else{
			cout<<"Escape possible in "<<ans<<" steps.\n";
		}
	}
	return 0;
}
```

### 時間複雜度分析
每筆測資輸入時間複雜度為 $O(nm)$
每筆測資 BFS 時間複雜度為 狀態數 $\times$ 操作的數量 $= (2^4nm) \times(4)$ 大約為 $O(nm)$
每筆測資總時間複雜度為 $O(nm)$

# Kattis fontan
## 題目
https://open.kattis.com/problems/fontan

給一個 $N \times M$ 的圖，上面有 `.`, `#`, `V` 三種元素，分別表示 空氣、石頭、水
水可以每次從上往下流動一個單位，但是當往下會遇到石頭的時候水會往兩側移動
現在告訴你一開始哪裡有水，請輸出水不再流動時圖的情況

## 想法
水的擴散情形就跟地圖上 BFS 一樣，每次都是全部擴散出去一格
每次檢查是否可以往下走，如果可以就往下，如果不行就檢查兩側，直到沒有水可以再移動就輸出答案

### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int n, m, S=0, que[2550][2];
int dx[] = {0, 0};
int dy[] = {-1, 1};
char arr[55][55];
bool vis[55][55];

void BFS(){
	for(int i=0, j=S, x, y, nx, ny ; i<j ; i++){
		x = que[i][0];
		y = que[i][1];
		
		// 先檢查往下
		nx = x + 1;
		ny = y;
		if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
		if(!vis[nx][ny] && arr[nx][ny] == '.'){
			vis[nx][ny] = true;
			que[j][0] = nx;
			que[j][1] = ny;
			arr[nx][ny] = 'V';
			j++;
		}
		// 是石頭就再檢查左右
		else if(!vis[nx][ny] && arr[nx][ny] == '#'){
			for(int k=0 ; k<2 ; k++){
				nx = x + dx[k];
				ny = y + dy[k];
				if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
				if(!vis[nx][ny] && arr[nx][ny] == '.'){
					vis[nx][ny] = true;
					que[j][0] = nx;
					que[j][1] = ny;
					arr[nx][ny] = 'V';
					j++;
				}
			}
		}
	}
}

int main(){
	for(int i=0 ; i<55 ; i++){
		for(int j=0 ; j<55 ; j++){
			vis[i][j] = false;
		}
	}
	cin>>n>>m;
	for(int i=0 ; i<n ; i++){
		for(int j=0 ; j<m ; j++){
			cin>>arr[i][j];
			if(arr[i][j] == 'V'){
				que[S][0] = i;
				que[S][1] = j;
				vis[i][j] = true;
				S++;
			}
		}
	}
	BFS();
	for(int i=0 ; i<n ; i++){
		for(int j=0 ; j<m ; j++){
			cout<<arr[i][j];
		}
		cout<<"\n";
	}
	return 0;
}
```

### 時間複雜度分析
輸入時間複雜度為 $O(nm)$
BFS 時間複雜度為 狀態數 $\times$ 操作的數量 $= (nm) \times 3$ 計為 $O(nm)$
總時間複雜度為 $O(nm)$

# Kattis pebblesolitaire
## 題目
https://open.kattis.com/problems/pebblesolitaire

題目包含多筆測資，每筆測資有一個字串，字串當中只會有 `-` 和 `o` 兩種字元
對於一個字串，如果有連續出現 `-oo` 或是 `oo-` ，我們可以選擇要不要把第一個以及最後一個交換，然後把中間換成 `-`
也就是 `-oo` -> `o--` ; `oo-` -> `--o`
請問經過多次這樣的操作之後，字串中最少可以只剩下多少 `o`

## 想法 By Koios
我們每次操作都必定只會讓 `o` 的數量減少，但是要在甚麼時機選擇進行操作是不明確的
這時候可以考慮枚舉，注意到每次 `o` 減少的數量都是固定的，那麼我們就可以用 BFS 來枚舉了
每次檢查字串中每個出現 `-oo` 以及 `o--` 的位置，只要操作後的字串過去沒有出現過就可以繼續枚舉

那麼要怎麼檢查字串有沒有用過?
可以用後面教到的位元運算來解決，我們用一個 int 的每個 bit 來記錄字串中某個位置是不是 `o`
例如 `--o` 就紀錄成 `001`，用十進位表示就是 `2`
字串長度固定會是 $12$，那麼我們只需要 $2^{12} = 4096$ 就可以紀錄全部的情況了

### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int n, stat;
string s, str, tmp, que[5000];
bool vis[5000];

int str_to_stat(string s){
	// 把字串轉換成數字的狀態
	int res = 0;
	for(int i=0 ; i<s.size() ; i++){
		if(s[i] == 'o'){
			res |= (1<<i);
		}
	}
	return res;
}

int BFS(){
	que[0] = s;
	vis[str_to_stat(s)] = true;
	
	int i, j=1;
	for(i=0, j=1 ; i<j ; i++){
		str = que[i];
		for(int k=0 ; k<str.size()-2 ; k++){
			if((str[k] == 'o' && str[k+1] == 'o' && str[k+2] == '-') || (str[k] == '-' && str[k+1] == 'o' && str[k+2] == 'o')){
				tmp = str;
				swap(tmp[k], tmp[k+2]);
				tmp[k+1] = '-';
				stat = str_to_stat(tmp);
				if(!vis[stat]){
					vis[stat] = true;
					que[j] = tmp;
					j++;
				} 
			}
		}
	}
	return j-1;
}

int main(){
	cin>>n;
	while(n--){
		for(int i=0 ; i<5000 ; i++){
			vis[i] = false;
		}
		cin>>s;
		int last = BFS();
		int ans = 0;
		for(int i=0 ; i<que[last].size() ; i++){
			if(que[last][i] == 'o') ans++;
		}
		cout<<ans<<"\n";
	}
	return 0;
}
```

### 時間複雜度分析
每筆測資輸入時間複雜度為 $O(1)$
BFS 時間複雜度為 狀態數 $\times$ 操作數量，最多為 $4096 \times 10$
假設字串長度是 $s$，那麼 BFS 時間複雜度估計為 $O(10 \times 2^s)$
總時間複雜度為 $O(2^s \times n)$

###### tags: `SCIST 演算法 題解`