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

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

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

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

题目链接：Catch That Cow
BFS：

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

思路：

æä½ç 有两点需要说明：

注意红色的叉，表示搜索过程已经搜索过的节点，这时要跳过。所以初始化BFS数组元素为-1表示未搜索状态
已经搜索过第i层的节点，那么第i+1层的搜索从哪个节点开始？这时需要设置一个队列，i层已经搜索过的节点入队（在对第i−1层的节点分叉时），然后依次作为第i+1层节点的父节点出队
- 代码：
  include
  include
  include
  using namespace std;
  
  define Max_Length 100001
  int N, M, Cur;
  
  int BFS[Max_Length], Elect[3];
  
  queue 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;
}