# Week 11 BFS

:::info
時間：04/30 9:00 ~ 17:00
地點：成大資工系新館 **65304** 教室
主題：BFS
直播連結：https://youtube.com/live/QdZruoWnPZo?feature=share
:::

# 必作題題解

[TOC]

## 三章_第二節

### TOJ 432 - Akechi 明智的選擇

撰寫：fishhh

這裡改用 BFS 來解，就 BFS 的裸題

:::spoiler

#include<iostream>
using namespace std;
int move_x[]={0,0,-1,1},move_y[]={1,-1,0,0};
int a,b,n,m,map[1002][1002]={},u,v,f;
void bfs(int pos_x,int pos_y,int sum){
    if(map[pos_x][pos_y]==-1){
        return ;
    }
    if(map[pos_x][pos_y]==0){
        map[pos_x][pos_y]=sum;
        int nx,ny;
        for(int i=0;i<4;i++){
            nx=pos_x+move_x[i];
            ny=pos_y+move_y[i];
            if(nx<1||ny<1||nx>n||ny>m){
                continue;
            }
            bfs(nx,ny,sum+1);
        }
    }
}
int main(){
    int x,y;
    cin>>n>>m>>x>>y>>u>>v>>f;
    for(int i=0;i<f;i++){
        cin>>a>>b;
        map[a][b]=-1;
    }
    bfs(x,y,0);
    if(map[u][v]==0){
        cout<<"Harakiri!\n";
    }
    else{
        cout<<"Cool!\n";
    }
}

:::

---

### UVa 439 - Knight Moves

撰寫：fishhh

這裡比較不一樣的是處理騎士走路的問題。主要就是 dx 和 dy 陣列比較不同。

:::spoiler

#include "iostream"
#include "queue"
using namespace std;
int main(){
    string x,y;
    while(cin>>x>>y){
        queue<pair<int,int>> q;
        int ans[10][10]={};
        bool vis[10][10]={};
        int tar_x=y[0]-'a',tar_y=y[1]-'0';
        tar_x++;
        int np_x=x[0]-'a',np_y=x[1]-'0';
        np_x++;
        int cx[]={-2,-1,1,2,2,1,-1,-2},cy[]={-1,-2,2,1,-1,-2,2,1};
        int nst=0;
        q.push({np_x,np_y});
        vis[np_x][np_y]=1;
        ans[np_x][np_y]=0;
        while(!q.empty()){
            int nl=q.size();
            for(int i=0;i<nl;i++){
                auto np=q.front();
                q.pop();
                ans[np.first][np.second]=nst;
                if(np.first==tar_x&&np.second==tar_y){
                    while(q.size())q.pop();
                    break;
                }
                for(int x=0;x<8;x++){
                    int nx=np.first+cx[x],ny=np.second+cy[x];
                    if(nx<=0||ny<=0||nx>=9||ny>=9)continue;
                    if(!vis[nx][ny]){
                        q.push({nx,ny});
                        vis[nx][ny]=1;
                    }
                }
            }
            nst++;
        }
        printf("To get from %s to %s takes %d knight moves.\n",x.c_str(),y.c_str(),nst-1);
    }
}

:::

---

### UVa 532 - Dungeon Master

撰寫：fishhh

這題比較不同的就是地圖變成3維了，其餘操作都相同。
可以練一下實作的能力~

:::spoiler

#include<queue>
#include<iostream>
using namespace std;
struct node{
	int x;
	int y;
	int z;	
};
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int l,r,c;
	string str;
	int map[40][40][40],el,er,ec;
	while(cin>>l>>r>>c){
		if(l==0&&r==0&&c==0){
			return 0;
		}
		queue<node> q;
		node tmp,now;
		bool vis[40][40][40]={};
		for(int il=0;il<l;il++){
			for(int ir=0;ir<r;ir++){
				cin>>str;
				for(int ic=0;ic<c;ic++){
					if(str[ic]=='#'){
						map[ic][ir][il]=-1;
						vis[ic][ir][il]=1;
					}
					else if(str[ic]=='.'){
						map[ic][ir][il]=0;
					}
					else if(str[ic]=='S'){
						map[ic][ir][il]=0;
						tmp.x=ic;
						tmp.y=ir;
						tmp.z=il;	
						vis[ic][ir][il]=1;
						q.push(tmp);
					}
					else{
						map[ic][ir][il]=0;
						el=il,er=ir,ec=ic;
					}
				}
			}
		}
		//input end
		int time=0,cx[]={0,0,-1,1},cy[]={-1,1,0,0};
		while(!q.empty()){
			int nl=q.size();
			for(int inl=0;inl<nl;inl++){
				node nxt;
				now=q.front();
				q.pop();
				nxt=now;
				if(map[now.x][now.y][now.z]==-1){
					continue;
				}
				map[now.x][now.y][now.z]=time;
				if(nxt.z-1>=0){
					nxt.z--;
					if(!vis[nxt.x][nxt.y][nxt.z]){
						vis[nxt.x][nxt.y][nxt.z]=1;
						q.push(nxt);	
					}
					nxt.z++;
				}
				if(nxt.z+1<l){
					nxt.z++;
					if(!vis[nxt.x][nxt.y][nxt.z]){
						vis[nxt.x][nxt.y][nxt.z]=1;
						q.push(nxt);	
					}
					nxt.z--;
				}
				for(int i=0;i<4;i++){
					nxt.x=now.x+cx[i],nxt.y=now.y+cy[i],nxt.z=now.z;
					if(nxt.x<0||nxt.y<0||nxt.x>=c||nxt.y>=r){
						continue;
					}
					if(!vis[nxt.x][nxt.y][nxt.z]){
						vis[nxt.x][nxt.y][nxt.z]=1;
						q.push(nxt);
					}
				}	
			}
			time++;
		}
//		for(int il=0;il<l;il++){
//			for(int ir=0;ir<r;ir++){
//				for(int ic=0;ic<c;ic++){
//					cout<<map[ic][ir][il]<<" ";
//				}
//				cout<<"\n";
//			}
//			cout<<"\n";
//		}
		if(map[ec][er][el]!=0){
			cout<<"Escaped in "<<map[ec][er][el]<<" minute(s).\n";
		}
		else{
			cout<<"Trapped!\n";
		}
	}
}

:::

---

### UVa 10102 - The path in the colored field

撰寫：fishhh

一開始可能會想說，對於每一個 1 做 BFS 找最短路。
分析一下複雜度，做一次 BFS 的時間是 $O(n^2)$ 然後最多有可能做 $O(n^2)$ (因為最多有 $n^2$ 個 1)
整體就是 $O(n^4)$ 接近 $10^8$ 雖然常數不大 但很可能 TLE。

又有另一個想法，把所有 1 跟 3 的座標抓出來，然後對於每個 1 去掃過一次所有 3 的座標( x,y 座標差就是他們之間最短距離! ) 就可以知道對於一個 1 的位置與 3 的最短距離!
然後全部的 1 都做一次然後取最大值，就可以知道答案了~

分析複雜度，最壞的情況有 $(n^2)/2$ 個 1 有 $(n^2)/2$ 個 3 (這樣乘起來才會盡量大)，所以複雜度會是 $O(n^4)$ 但嚴格來說這個會快一點點啦XD。

其實實際上還是跟找最短路徑一樣，反正就是把所有起點都 push 進 queue 裡面，然後做一次 BFS 就好~

:::spoiler

#include<bits/stdc++.h>
using namespace std;

struct Node {
    int x, y, dis;
};

char board[110][110];
bool used[110][110];
Node q[2000000];
int m, dx[4]={0,1,0,-1}, dy[4]={1,0,-1,0};

int bfs(int start_y, int start_x) {
    Node current, next;
    memset(used, false, sizeof(used));
    q[0].y = start_y;
    q[0].x = start_x;
    q[0].dis = 0;

    for (int i = 0, j = 1; i < j; i++) {
        current = q[i];

        if (board[current.y][current.x] == '3') {
            return current.dis;
        } else {
            for (int k = 0; k < 4; k++) {
                next = current;
                next.x += dx[k];
                next.y += dy[k];
                next.dis++;

                if (next.x >= 0 && next.x < m && next.y >= 0 && next.y < m) {
                    if (!used[next.y][next.x]) {
                        used[next.y][next.x] = true;
                        q[j] = next;
                        j++;
                    }
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    while (cin >> m) {
        vector<int> distances;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                cin >> board[i][j];
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == '1') {
                    distances.push_back(bfs(i, j));
                }
            }
        }

        sort(distances.begin(), distances.end());
        cout << distances.back() << "\n";
    }

    return 0;
}

:::

---