POJ 3278 Catch That Cow BFS（第一題）

【題意簡述】：一個農夫和一頭牛在同一坐標軸上，且已知坐標，農夫可以從坐標是x的點移動到x-1、x+1和x*2，求最少幾步可以抓到牛。

【思路】：這是我的第一道有關BFS的搜索題！(BFS常用於解決最優可行解問題！而且通常應用隊列這一數據結構)

我小心翼翼去完成這道經典的題，所以參考了，很多資料。精華部分，我都摘錄下來至此：

我們已經知道此題給我我們一個起點和一個終點，每個點都能到達的狀態是x-1、x+1、x*2，對於每一個狀態都可以到達3個子狀態，因此從起點開始，第二層狀態就有3個，第三層就有9個……，這樣下去，直到搜索到終點結束，那麼求出的步數就可以達到最小！

因為對於相同層的狀態，所需的步數是相同的，而且對於層與層之間的狀態來說，先搜索完的前一層的所有狀態才開始下一層的搜索。也就是說前一個節點的步數一定小於等於後一個節點的步數。所以當第一次到達終點的時候，就得到了最短的路徑。。但是如果這樣硬搜的話便會超時，所以 又是剪枝！！剪枝是很重要的，剪枝這個東西就是靠多積累！多做題！多感受！

// 1592K 47Ms
#include
#include
#include
using namespace std;

struct node        // 構造節點！！ 
{
	int num;
	int count;
	node(){}
	node(int n,int c)
	{
		num = n;
		count = c;
	}
};

node queue[1000000];
bool visit[200010];

int bfs(int n,int k)
{
	if(n ==k )  return 0;   //此處注意，是個特例！ 
	node n0(n,0);
	memset(visit,false,sizeof(visit));
	int top = 0,end = 0;
	queue[end++] = n0;
	visit[n] = true;
	while(top != end)
	{
		node temp = queue[top++];
		if(top >= 1000000) top = 0;
		node n1(temp.num - 1,temp.count+1);
		node n2(temp.num + 1,temp.count+1);
		node n3(temp.num * 2,temp.count+1);
		if(n1.num == k) return n1.count;
		if(n2.num == k) return n2.count;
		if(n3.num == k) return n3.count;
		if(n1.num<150005&n1.num >= 0&&!visit[n1.num]){
			// 注意剪枝條件！，不然很可能TLE
			// 當超過150005時就不用考慮了！！
			// 當小於0時也不必考慮
			// 已經搜索過的節點也不必考慮
			// 以上這些就是剪枝部分！！
			queue[end++] = n1;
			if(end >= 1000000) end = 0; //循環隊列！
			visit[n1.num] = true; 
		}
		if(n2.num < 150005 && n2.num >= 0 && !visit[n2.num]){
			queue[end++] = n2;
			if(end >=1000000) end = 0;
			visit[n2.num] = true;
		}
		if(n3.num <150005&&n3.num >= 0&&!visit[n3.num])
		{
			queue[end++] = n3;
			if(end>=1000000) end = 0;
			visit[n3.num] = true;
		}
	}
}

int main()
{
	int n,k;
	
	cin>>n>>k;
	cout<