USACO 2007 Open Silver

问题链接：。

题意简述：一条线上，人的FJ的起点为K位置，牛在N位置（牛不动），输入正整数K和N。若FJ在x位置，FJ有三种走法，分别是走到x-1、x+1或2x位置。求从K走到N的最少步数。

问题分析：典型的BFS问题。在BFS搜索过程中，走过的点就不必再走了，因为这次再走下去不可能比上次的步数少。

程序说明：

程序中，使用了一个队列来存放中间节点。

需要说明的是，除了BFS方法，这个题应该可以用分支限界法来解，需要更高的技巧。

AC的C++语言程序如下：

/* POJ3278 HDU2717 Catch That Cow */#include 
    
     #include 
     
      #include 
      
       using namespace std;const int MAXN = 100000;const int MAXN2 = MAXN * 2;bool notvist[MAXN * 2 + 2];int n, k, ans;struct node {    int p, level;};node start;void bfs(){    queue
       
         q;    int nextp;    memset(notvist, true, sizeof(notvist));    notvist[n] = false;    start.p = n;    start.level = 0;    ans = 0;    q.push(start);    while(!q.empty()) {        node front = q.front();        q.pop();        if(front.p == k) {            ans = front.level;            break;        }        nextp = front.p - 1;        /* x-1 */        if(nextp >= 0 && notvist[nextp]) {            notvist[nextp] = false;            node v;            v.p = nextp;            v.level = front.level + 1;            q.push(v);        }        nextp = front.p + 1;        /* x+1 */        if(nextp <= MAXN2 && notvist[nextp]) {            notvist[nextp] = false;            node v;            v.p = nextp;            v.level = front.level + 1;            q.push(v);        }        nextp = front.p + front.p;      /* 2x */        if(nextp <= MAXN2 && notvist[nextp]) {            notvist[nextp] = false;            node v;            v.p = nextp;            v.level = front.level + 1;            q.push(v);        }    }}int main(){    while(cin >> n >> k) {        bfs();        printf("%d\n", ans);    }    return 0;}