首页 > 代码库 > poj3278(BFS)

poj3278(BFS)

题意:给出两个点代表人和牛的位置,人的运动方式有三种,牛原地不用,问人赶到牛的位置的最快速度;

key:刚开始找规律,其实规律都没规律,六组数据都过了那个碰巧。用bfs,搜到牛的位置结束,并返回步数(每个操作算一步)。注意牛可在人的左右边,要分开两种情况。

#include <iostream>#include <stdio.h>#include <string.h>#include <queue>const int maxn = 100000 + 5;int visit[maxn];  //标记是否访问int step[maxn];   //步数using namespace std;bool ok(int x)          //判断是否超出数据范围{    if(x < 0 || x > 100001)        return 1;    else        return 0;}int bfs(int a, int b){    int head, next;    memset(visit, 0, sizeof(visit));    memset(step, 0, sizeof(step));    queue <int> que;                //定义一个名为que的队列    que.push(a);                     //将第一个数放进队列里    visit[a] = 1;                     //标记这个点已经访问过    step[a] = 0;                       //起初步数为0    while(que.size()){                      //判断队列是否为空,也可以表示为 !que.empty()        head = que.front();                 //将最前端的元素取出        que.pop();        for(int i = 0; i < 3; i++){             //有三种运动方式            if(i == 0) next = head - 1;            if(i == 1) next = head + 1;            if(i == 2) next = 2 * head;            if(ok(next)) continue;     //如果超出范围即结束本次循环            if(!visit[next]){             //如果这点没有访问过,                que.push(next);                 //即把该点放进队列中,                step[next] = step[head] + 1;        //计算步数                visit[next] = 1;                    //标记已经访问            }            if(next == b)                           //找到终点,就返回走到该点时的步数                return (step[next]);        }    }}int main(){    int n, m;    scanf("%d%d", &n, &m);    if(n >= m)               //如果n > m只有一种运动方式        printf("%d\n", n - m);    else                        //否则用广搜得到答案        printf("%d\n", bfs(n, m));    return 0;}

 

poj3278(BFS)