HDU_2717 Catch That Cow(BFS)

　　开始没整明白，还想用dfs递归求解，后来看了看解题报告的思路（貌似这题可以用dp），bfs一遍，用一个best[i]存放到i的最优解，最后直接输出best[k]就行。第一次队列数组开小（还是不想用<queue>）了，WA了一次。。。

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 100007;

int q[N*10];
int best[N];
int n, k;

void bfs()
{
    int f = 0, r = 0, x, next;
    q[r++] = n;
    
    while(f < r)
    {
        x = q[f++];
        if(x == k)
            break;

        next = x-1;    
        if(next > 0 && !best[next])
        {
            q[r++] = next;
            best[next] = best[x] + 1;
        }

        next = x + 1;
        if(!best[next])
        {
            q[r++] = next;
            best[next] = best[x] + 1;
        }

        next = x*2;
        if(next <= N-7 && next - k < k - x && !best[next])
        {
            q[r++] = next;
            best[next] = best[x] + 1;
        }
    }
}

int main()
{
    //freopen("data.in", "r", stdin);

    while(~scanf("%d%d", &n, &k))
    {
        memset(best, 0, sizeof(best));
        if(n >= k)
            printf("%d\n", n-k);
        else
        {
            bfs();
            printf("%d\n", best[k]);
        }
    }
    return 0;
}