- 1#include 2#include 3#include 4#include < string.h > 5#include 6#define MAX 100001 7 using namespace std;
- 8 queue < int > q; //使用前需定义一个queue变量,且定义时已经初始化
- 9 bool visit[MAX]; //访问空间
- 10 int step[MAX]; //记录步数的数组不能少
- 11 bool bound(int num) //定义边界函数
- 12 {
- 13
- if (num < 0 || num > 100000) 14
- return true;
- 15
- return false;
- 16
- }
- 17 int BFS(int st, int end) 18 {
- 19 queue < int > q; //使用前需定义一个queue变量,且定义时已经初始化
- 20 int t,
- temp;
- 21 q.push(st); //进队列
- 22 visit[st] = true;
- 23
- while (!q.empty()) //重复使用时,用这个初始化
- 24 {
- 25 t = q.front(); //得到队首的值
- 26 q.pop(); //出队列,弹出队列的第一个元素,并不会返回元素的值
- 27
- for (int i = 0; i < 3; ++i) //三个方向搜索
- 28 {
- 29
- if (i == 0) 30 temp = t + 1;
- 31
- else if (i == 1) 32 temp = t - 1;
- 33
- else 34 temp = t * 2;
- 35
- if (bound(temp)) //越界
- 36
- continue;
- 37
- if (!visit[temp]) //访问空间未被标记
- 38 {
- 39 step[temp] = step[t] + 1;
- 40
- if (temp == end) 41
- return step[temp];
- 42 visit[temp] = true; //标记此点
- 43 q.push(temp); //将temp元素接到队列的末端;
- 44
- }
- 45
- }
- 46
- }
- 47
- }
- 48 int main() 49 {
- 50 int st,
- end;
- 51
- while (scanf("%d%d", &st, &end) != EOF) 52 {
- 53 memset(visit, false, sizeof(visit)); //visit数组进行初始化操作
- 54
- if (st >= end) 55 cout < endl;
- 56
- else 57 cout < endl;
- 58
- }
- 59
- return 0;
- 60
- }
来源: http://www.bubuko.com/infodetail-2033504.html