# BFS

# 想法

BFS 廣度優先走訪，顧名思義，在我們尋找解答時，就像是在 RPG 上解任務一樣，將每個相同等級層數的任務做完，並將其開通的子任務子節點都記錄下來，等做完同等級的之後，在往下把下一個等級的任務解掉，直到所有任務都做完。

運用迴圈的方式，從第一個點開始將鄰近的點加入佇列內部，等到點都加入完後，就往下推找佇列中的下個點，直到佇列的每個點都被探詢過。

用於尋找兩個節點之間的最短路徑、查找各點之間所有相鄰的點，以及測試圖是否為二分圖等。

給你一個 NXN 格的迷宮，迷宮中以 #代表障礙物，以。代表路，求包括起點和終點，最少路徑的長度。

	#include<bits/stdc++.h>
	using namespace std;
	int Maze[100][100];// 紀錄最少步數

	struct point{
	int x,y;
	};

	int main() {
	point k,next;
	int N;
	while(cin>>N) {
	queue<point> qu;
	for(int y=0;y<N&&getchar();y++)
	for(int x=0;x<N;x++){
	scanf("%c",&Maze[y][x]);
	Maze[y][x]=(Maze[y][x]=='.'?-1:-2);
	}
	k.x=1,k.y=1;
	qu.push(k);
	Maze[1][1]=1;
	while(!qu.empty()) {
	k = qu.front();qu.pop();
	next.x=k.x-1,next.y=k.y;
	if(Maze[next.y][next.x]==-1)
	qu.push(next),Maze[next.y][next.x]=Maze[k.y][k.x]+1;
	next.x=k.x+1,next.y=k.y;
	if(Maze[next.y][next.x]==-1)
	qu.push(next),Maze[next.y][next.x]=Maze[k.y][k.x]+1;
	next.x=k.x,next.y=k.y-1;
	if(Maze[next.y][next.x]==-1)
	qu.push(next),Maze[next.y][next.x]=Maze[k.y][k.x]+1;
	next.x=k.x,next.y=k.y+1;
	if(Maze[next.y][next.x]==-1)
	qu.push(next),Maze[next.y][next.x]=Maze[k.y][k.x]+1;
	}
	if(Maze[N-2][N-2]>0) printf("%d\n",Maze[N-2][N-2]);
	else printf("No solution!\n");
	}
	return 0;
	}

給你一個數字 S，你可以將 A 轉換成 B 藉由加上一個 X，X 是一個 A 的質因數 (1 跟 A 不考慮進去)，現在你的工作就是找出最少需要轉換次數把 S 轉換成 T

使用 BFS 將所有 S+X 的狀況都加到佇列內部，並記錄下次數，直到找到 T 為止，記得，如果有記錄過 S+X 狀況的話，就不需要再紀錄一次！！

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

	int primes[1050], pointer, S, T, minn, cases, buffer1, buffer2;
	bool notprime[1050] = { true, true };

	void Initialize() {
	for (int i = 2; i < 1050; i++) {
	if (!notprime[i])
	primes[pointer++] = i;
	for (int j = 0; i * primes[j] < 1050 && j < pointer; j++)
	notprime[i * primes[j]] = true;
	}
	}

	int main() { cin.sync_with_stdio(false), cin.tie(0), cout.tie(0); Initialize();
	queue <int> BFS, times;
	while (cin >> S >> T, S \|\| T) {
	cout << "Case " << ++cases << ": ";
	if (S == T) cout << "0\n";
	else {
	bool have[1001] = {};
	BFS.push(S), times.push(1), have[S] = true, minn = 2147483647;
	while (!BFS.empty()) {
	buffer1 = BFS.front(), buffer2 = sqrt(buffer1);
	for (int i = 0; primes[i] < buffer1; i++)
	if (!(buffer1 % primes[i])) {
	buffer2 = buffer1 + primes[i];
	if (buffer2 < T && !have[buffer2])
	BFS.push(buffer2), times.push(times.front() + 1), have[buffer2] = true;
	else if (buffer2 == T && times.front() < minn)
	minn = times.front();
	}
	BFS.pop(), times.pop();
	}
	if (minn == 2147483647) cout << "-1\n";
	else cout << minn << '\n';
	}
	}
	}