首页 > 代码库 > POJ 3287 (基础BFS) Catch That Cow

POJ 3287 (基础BFS) Catch That Cow

2024-07-16 14:12:09   224人阅读

这是做的第一道BFS，很基础很简单的题目

广度优先搜索算法如下：（用QUEUE）
(1) 把初始节点S0放入Open表中；
(2) 如果Open表为空，则问题无解，失败
退出；
(3) 把Open表的第一个节点取出放入
Closed表，并记该节点为n；
(4) 考察节点n是否为目标节点。若是，
则得到问题的解，成功退出；
(5) 若节点n不可扩展，则转第(2)步；
(6) 扩展节点n，将其不在Closed表和
Open表中的子节点(判重）放入Open表的尾部
，并为每一个子节点设置指向父节点的指针(
或记录节点的层次），然后转第(2)步。

 

一层一层的往深了的搜索，直到遇到所求解。那么深度就是最短步数，还有要注意判重，其中visited数组就起到了判重的作用。

 

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <queue> 5 using namespace std; 6 int n, k; 7 const int maxn = 100000; 8 int visited[maxn + 10];    //判重标记 9 struct Step10 {11     int x;12     int steps;13     Step(int xx, int s):x(xx), steps(s){}14 };15 queue<Step> q;16 int main(void)17 {18     scanf("%d%d", &n, &k);19     memset(visited, 0, sizeof(visited));20     q.push(Step(n, 0));21     visited[n] = 1;22     while(!q.empty())23     {24         Step s = q.front();25         if(s.x == k)26         {//找到目标27             printf("%d\n", s.steps);28             return 0;29         }30         else31         {32             if(s.x - 1 >= 0 && !visited[s.x-1])33             {34                 q.push(Step(s.x-1, s.steps+1));35                 visited[s.x-1] = 1;36             }37             if(s.x + 1 <= maxn && !visited[s.x+1])38             {39                 q.push(Step(s.x+1, s.steps+1));40                 visited[s.x+1] = 1;41             }42             if(s.x*2 <= maxn && !visited[s.x*2])43             {44                 q.push(Step(s.x*2, s.steps+1));45                 visited[s.x*2] = 1;46             }47             q.pop();48         }49     }50     return 0;51 }
代码君

 


联系
我们