| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
POJ 3278 Catch That Cow 这道题不知哪错了,请指教一下,看了好多代码,多谢了!!这道题不知道拿错了,看了很多别人的代码,思路一样,实现的方法也有一样但是就是WA了,测试了很多数据,都对。请大家帮忙看看。多谢了
#include <stdio.h>
#define MAX 200009
struct node
{
int depth; //这是用来记录步数的或者说是第几层
int data; //这是用来记录生成的数据的。
}q[MAX];
int flag[MAX];
int front,rear;
int n,k;
void bfs()
{
int e,ddepth=0;
front=rear=0;
flag[n]=1;
rear=(rear+1)%MAX;
q[rear].data=n;
q[rear].depth=ddepth;
while(front!=rear)
{
front=(front+1)%MAX;
e=q[front].data;
ddepth=1+q[front].depth; //ddepth是用来记录即将要生成的几个数是第几层的(第几步的)。
if(e==k)
{
printf("%d\n",q[front].depth);
break;
}
else //三种操作及相应的剪枝
{
if(e+1<(2*k-n)&&flag[e+1]==0)
{
flag[e+1]=1;
rear=(rear+1)%MAX;
q[rear].data=e+1;
q[rear].depth=ddepth;
}
if(e-1>(n/2)&&flag[e-1]==0)
{
flag[e-1]=1;
rear=(rear+1)%MAX;
q[rear].data=e-1;
q[rear].depth=ddepth;
}
if(e*2<(2*k-n)&&flag[e*2]==0)
{
flag[e*2]=1;
rear=(rear+1)%MAX;
q[rear].data=e*2;
q[rear].depth=ddepth;
}
}
}
}
void init()
{
int i;
for(i=0;i<=MAX;i++)
{
flag[i]=0;
q[i].depth=0;
}
}
int main()
{
while(scanf("%d%d",&n,&k)!=EOF)
{
init();
if(n>=k)
{
printf("%d\n",n-k);
}
else
{
bfs();
}
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator