BFS的一道水题,上学之前AC掉:-) 直接BFS即可
/* * HDU-???? catch that cow * mike-w * 2012-9-25 */ #include<stdio.h> #include<stdlib.h> #include<string.h> #define QSIZE 222222 int que[QSIZE], qhead, qtail, qlen; int rec[QSIZE]; int enque(int e) { qlen++; que[qtail++]=e; qtail%=QSIZE; return 0; } int deque(void) { int ret=que[qhead++]; qhead%=QSIZE; qlen--; return ret; } int main(void) { int n, k, x; while(scanf("%d%d", &n, &k)!=EOF) { qhead=qtail=qlen=0; memset(rec, 0, sizeof(rec)); memset(que, 0, sizeof(que)); enque(n); while(qlen>0) { x=deque(); if(x==k) break; if(x+1<=2*k && !rec[x+1]) rec[x+1]=rec[x]+1, enque(x+1); if(x-1>=0 && !rec[x-1]) rec[x-1]=rec[x]+1, enque(x-1); if(x<=k && !rec[2*x]) rec[2*x]=rec[x]+1, enque(2*x); } printf("%d\n", rec[x]); } return 0; }