抓住那头牛 [OpenJ_Bailian – 4001]

抓住那头牛 [OpenJ_Bailian – 4001]


https://cn.vjudge.net/problem/OpenJ_Bailian-4001#author=malic

一般找最短方案都是用广度优先搜索,不只是图算法里有广度优先算法,对解空间进行遍历也可以使用BFS进行搜索。
简单情形,猫初始在X号箱子,它想去的Y号箱子比X的号码小,这时它只能逐个箱子的走过去,这时直接输出X-Y.
其它情形,就进行广度优先搜索,第k次移动处于位置x的时候,第k+1次移动可能处于x+1,x-1或2x,为节省时间,要保证x+1,x-1和2x以前没走过,这儿加个数组判断这个点x+1,x-1,2x以前是否没走到,若没走到的话就走过去。可以设定一个结构体记下当前的移动次数level和坐标data,初始data=X,level=0放入队列,从队列出取一个数,检查x+1,x-1,2x是否没有被访问过,没访问过的就以level=level+1和相应data入队,直到发现data=Y的时候,输出移动步数level并终止程序. 

#include <cstdio>
#include <queue>
#define MAXN 100003
using namespace std;

struct qNode
{
    int data;
    int level;
};

int main(void)
{
    bool visited[MAXN]={0};
    queue<qNode> q;
    qNode *p,*n1,*n2,*n3;
    int start,target;
    scanf("%d%d",&start,&target);
    if(start>=target)
    {
        printf("%d\n",start-target);
    }
    else
    {
        p=new qNode;
        n1=new qNode;
        n2=new qNode;
        n3=new qNode;
        p->data=start;
        p->level=0;
        visited[start]=true;
        q.push(*p);
        while(q.size()>0)
        {
            *p=q.front();
            q.pop();

            if(p->data==target)
            {
                printf("%d\n",p->level);
                break;
            }
            if( p->data+1<MAXN && visited[p->data+1]==false)
            {
                n1->data=p->data+1;
                visited[p->data+1]=true;
                n1->level=p->level+1;
                q.push(*n1);
            }
            if( p->data-1>=0 && visited[p->data-1]==false)
            {
                n2->data=p->data-1;
                visited[p->data-1]=true;
                n2->level=p->level+1;
                q.push(*n2);
            }
            if(p->data*2<MAXN && visited[p->data*2]==false)
            {
                n3->data=p->data*2;
                visited[p->data*2]=true;
                n3->level=p->level+1;
                q.push(*n3);
            }
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注