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