| ||||||||||
| 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 | |||||||||
bfs#include <stdio.h>
#include <string.h>
#define l 100010
int flag[l*4];
int head,tail;
struct point
{
int num;
int cut;
};
struct point q[l];
int s,e;
void bfs()
{
int temp;
memset(flag,0,sizeof(flag));
flag[s]=1;
head=0;
tail=0;
q[head].num=s;
q[head++].cut=0;
while(head!=tail)
{
temp=q[tail].num;
if(temp==e)
break;
else
{
if(temp-1>=0&&temp-1<=l&&!flag[temp-1])
{
flag[temp-1]=1;
q[head].num=temp-1;
q[head++].cut=q[tail].cut+1;
}
if(temp+1>=0&&temp+1<=l&&!flag[temp+1])
{
flag[temp+1]=1;
q[head].num=temp+1;
q[head++].cut=q[tail].cut+1;
}
if(2*temp>=0&&2*temp<=l&&!flag[2*temp])
{
flag[2*temp]=1;
q[head].num=2*temp;
q[head++].cut=q[tail].cut+1;
}
}
tail++;
}
printf("%d\n",q[tail].cut);
}
int main()
{
while(scanf("%d %d",&s,&e)!=EOF)
{
bfs();
}
return 1;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator