hdu 2717 Catch That Cow(BFS,剪枝)

题目

 

hdu 2717 Catch That Cow(BFS,剪枝)
#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std;
struct tt
{
    int step,tem;
};
int visit[100010];
queue <tt> q;

int bfs(tt s,tt e)
{
    tt front,temp;
    q.push(s);
    visit[s.tem]=1;
    while(!q.empty())
    {
        front=q.front();
        q.pop();
        temp.step=front.step+1;
        temp.tem=front.tem+1;
        if(temp.tem==e.tem)
            return temp.step;
        else if(temp.tem>=0&&temp.tem<=100000&&visit[temp.tem]==0) q.push(temp),visit[temp.tem]=1;
        
        temp.tem=front.tem-1;
        if(temp.tem==e.tem)
            return temp.step;
        else if(temp.tem>=0&&temp.tem<=100000&&visit[temp.tem]==0) q.push(temp),visit[temp.tem]=1;
        
        temp.tem=front.tem*2;
        if(temp.tem==e.tem)
            return temp.step;
        else if(temp.tem>=0&&temp.tem<=100000&&visit[temp.tem]==0) q.push(temp),visit[temp.tem]=1;
    }
    return 0;
}

int main()
{
    tt s,e;
    int ans;
    while(scanf("%d%d",&s.tem,&e.tem)!=EOF)
    {
        s.step=0;
        memset(visit,0,sizeof(visit));
        while(!q.empty())
            q.pop();
        if(s.tem<e.tem)
            ans=bfs(s,e);
        else
            ans=s.tem-e.tem;
        printf("%d\n",ans);
    }
    return 0;
}
View Code

hdu 2717 Catch That Cow(BFS,剪枝)

上一篇:Media Queries 媒体特性 实现响应式


下一篇:HDU 2492 PingPong