HDU 2717. 结构体队列 + BFS
原题链接
简单
作者:
史一帆
,
2021-04-22 16:24:07
,
所有人可见
,
阅读 302
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 100010;
int map[N]; //走过的标记1.没走过的标记0
int n, k; //n是农夫的位置,k是母牛的位置
struct node //定义一个结构体记录位置和步数
{
int x,step;
};
//check函数结果如果是0的话,第一就是越界,第二个就是这个点已经走过了
int check(int x)
{
if(x < 0 || x >= N || map[x])
return 0;
return 1;
}
int bfs(int x)
{
queue<node> q; //把q队列化
node a, next; //把a,next作为结构体
a.x = x; //结构体a初始化
a.step = 0;
map[x] = 1; //刚开始的点标记为1
q.push(a); //把a加入到队列的末尾
while(!q.empty())
{
a = q.front(); //先把队首读取
q.pop(); //弹出队首
if(a.x == k) //如果农夫的位置和母牛的位置相同的话
return a.step; //直接返回步数
next = a;
//每次都将三种状况加入队列之中
//1.这个是+1的情况
next.x = a.x + 1;
if(check(next.x)) //无论是什么情况下这几行代码都是一样的
{
next.step = a.step + 1; //这个就是步数+1
map[next.x] = 1; //表示已经走过了这个点
q.push(next); //把next结构体加入队列
}
next.x = a.x - 1;
if(check(next.x))
{
next.step = a.step + 1;
map[next.x] = 1;
q.push(next);
}
next.x = a.x * 2;
if(check(next.x))
{
next.step = a.step + 1;
map[next.x] = 1;
q.push(next);
}
}
}
int main()
{
int ans; //统计最后的步数
while(cin >> n >> k) //n指的是农夫的位置,k指的是母牛的位置
{
memset(map, 0, sizeof (map)); //数组初始化
ans = bfs(n);
cout << ans << endl;
}
return 0;
}