电子商务与网络营销题库seo站长论坛

http://poj.org/problem?id=3278

就是农场主在X轴上找牛，给定牛的坐标，扭不动，农场主可以 +1 -1 *2 的方式前进，求最少的步数使其找到牛。

分三种情况走，直到遇到牛即可，同时为了避免不断的重复于某一点，记录到达该点的最短距离。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#define maxn 100007
#define inf 9999999
using namespace std;int ans,s,e;
struct node
{int len;int pos;
}p[maxn];//用来记录到达该点的最短距离//判断是否出界
bool isok(int x)
{if (x >= 0 && x <= 100000) return true;else return false;
}
int bfs()
{int i;int sum = 0;node ss;ss.len = 0;ss.pos = s;p[s].len = 1;queue<node>q;q.push(ss);while (!q.empty()){node cur = q.front(); q.pop();if (cur.pos == e){sum = cur.len;break;}node t;for (i = 0; i < 3; ++i){if (i == 0 && isok(cur.pos + 1)){t.pos = cur.pos + 1;if (p[t.pos].len > cur.len + 1){t.len = cur.len + 1;p[t.pos].len = cur.len + 1;q.push(t);}}if (i == 1 &&  isok(cur.pos - 1)){t.pos = cur.pos - 1;if (p[t.pos].len > cur.len + 1){t.len = cur.len + 1;p[t.pos].len = cur.len + 1;q.push(t);}}if (i == 1 &&  isok(cur.pos*2)){t.pos = cur.pos*2;if (p[t.pos].len > cur.len + 1){t.len = cur.len + 1;p[t.pos].len = cur.len + 1;q.push(t);}}}}return sum;
}
int main()
{for (int i = 0; i <= 100000; ++i) p[i].len = inf;scanf("%d%d",&s,&e);int ans = bfs();printf("%d\n",ans);return 0;
}