BFS(广度优先搜索)-POJ3278-Catch That Cow(抓住那头牛)

Myth丶恋晨 2022-05-17 02:16 151阅读 0赞

*  # BFS(广度优先搜索)-POJ3278-Catch That Cow(抓住那头牛) #

--------------------

*  ## 题目链接：[Catch That Cow][] ##
 *  ## BFS： ##

广度优先搜索(Breadth First Search, BFS)是对树的逐层遍历，通过**距终点状态由远到近对所有可能的状态进行搜索并剪枝**，**一般用于求解达到某目标的最小步骤数**。

思路：

![æä½ç][SouthEast] 有两点需要说明：  
1. 注意红色的叉，**表示搜索过程已经搜索过的节点**，这时要跳过。 所以***初始化BFS数组元素为-1表示未搜索状态***  
2. 已经搜索过第i层的节点，那么第i+1层的搜索从哪个节点开始？这时**需要设置一个队列**，**i层已经搜索过的节点入队（在对第i−1层的节点分叉时），然后依次作为第i+1层节点的父节点出队**

*  ## 代码： ##

#include<iostream>	
    #include<algorithm>	
    #include<queue>	
    using namespace std;
    #define Max_Length 100001
    
    int N, M, Cur;
    
    int BFS[Max_Length], Elect[3];
    
    queue<int> Level_Data;
    
    void Do_BFS()
    {
    	fill(BFS, BFS + Max_Length, -1);
    
    	Level_Data.push(N);
    	BFS[N] = 0;
    
    	while (!Level_Data.empty())
    	{
    		Cur = Level_Data.front();
    		Level_Data.pop();
    
    		if (M == Cur)		//走到终点M，完成跳出
    			break;
    		
    		Elect[0] = Cur - 1;
    		Elect[1] = Cur + 1;
    		Elect[2] = Cur * 2;
    		
    
    		for (int i = 0; i < 3; i++)
    		{
    			if (Elect[i] >= 0 && Elect[i]<Max_Length && BFS[Elect[i]] == -1)	//DFS[Elect[i]]==-1表示当前状态Elect[i]之前没有访问过,同时保证数据不能越界
    			{
    				Level_Data.push(Elect[i]);
    				BFS[Elect[i]] = BFS[Cur] + 1;		//当前状态Cur走向下一步
    			}
    		}
    	}
    	cout << BFS[M] << endl;	//输出结果
    }
    
    int main()
    {
    
    	cin >> N >> M;
    	Do_BFS();
    	return 0;
    }

*  ## 参考： ##

[Florence\_Janie-抓住那头牛(POJ NO.2971)][Florence_Janie-_POJ NO.2971]

[valval-广度优先搜索bfs与抓住那头奶牛(Catch that cow, poj3278)][valval-_bfs_Catch that cow_ poj3278]

[Catch That Cow]: http://poj.org/problem?id=3278
[SouthEast]: /images/20220517/f42d053254cd44b1a2797ba96952786d.png
[Florence_Janie-_POJ NO.2971]: https://blog.csdn.net/qq_34690929/article/details/77461552#question
[valval-_bfs_Catch that cow_ poj3278]: https://www.xuebuyuan.com/2138923.html