POJ 3278 Catch That Cow（BFS 剪枝）

這幾次都是每天的第一道題都挺順利，然後第二道題一卡一天。 = =，今天的這道題7點40就出來了，不知道第二道題在下午7點能不能出來。0 0

先說說這道題目，大意是有個農夫要抓牛，已知牛的坐標，和農夫位置。而且農夫有三種移動方式，X + 1，X - 1，X * 2，問最少幾步抓到牛。

開始認為很簡單的，三方向的BFS就能順利解決，然後在忘開標記的情況下直接廣搜，果然TLE，在你計算出最少位置之前，牛早跑了。

然後反應過來開標記，來節約時間，然後發現居然RE了，估計是標記數組不夠大，畢竟有一個方向的x * 2。

然後打算控制一下查找范圍，因為當X到達某個范圍之後，在變為K，肯定不會是最少路徑。

比如，當X已經大於K了，再執行X + 1， X * 2,肯定不會最短的得到K，然後在判斷標記的時候做了優化。

然後就過掉了。

我再去百度，看看有沒有更好的方法，發現我這個方法就叫剪枝啊 = =。嚇尿、

代碼如下：

#include 
#include 
#include 
#include 

#define LEN 1000000
struct node
{
    int num,t;
}q[LEN];

bool vis[10000000];

int bfs (int x,int k)
{
    int s = 0,e = 0;

    q[s].num = x;
    q[s++].t = 0;
    vis[x] = 1;
    while (s != e)
    {
        struct node tmp = q[e++];
        e %= LEN;

        if (tmp.num == k)
            return tmp.t;

        if (!vis[tmp.num + 1] && tmp.num <= k)
        {
            q[s].num = tmp.num + 1;
            q[s++].t = tmp.t +1;
            s %= LEN;
            vis[tmp.num + 1] = 1;
        }

        if (!vis[tmp.num - 1] && tmp.num - 1 >= 0)
        {
            q[s].num = tmp.num - 1;
            q[s++].t = tmp.t +1;
            s %= LEN;
            vis[tmp.num - 1] = 1;
        }

        if (!vis[tmp.num * 2] && tmp.num <= k)
        {
            q[s].num = tmp.num * 2;
            q[s++].t = tmp.t +1;
            s %= LEN;
            vis[tmp.num * 2] = 1;
        }
    }

    return -1;
}

int main()
{
    int x,k;

    while (~scanf (%d%d,&x,&k))
    {
        int ans = bfs (x,k);

        printf (%d
,ans);
    }
    return 0;
}