# 演算法課程題解 - 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}$，並且都有一個顏色，如附圖
一開始這個輪子都是以**綠色**觸碰地面
在一張地圖上有起點、終點、障礙物，現在輪子在起點朝向北方，每次你可以選擇要 **前進**、**右轉$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 演算法 題解`
Sign in with Wallet
Connect another wallet