本文共 2952 字,大约阅读时间需要 9 分钟。
我的第一道BFS,居然让我有种想杀人的冲动,题目上给的是100000,我不小心在程序里的限制条里,写成了1000000(别数了,多了一个零),本来,啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊!一天的时间。。。。。。。算了,不抱怨了,为了这道题,还把媛姐的代码看了好几遍,发现就计数方法不同啊!她的能过,我的为什么就过不去啊!唉,一个零。。。。
我的计数:每一层记一次数,最后记录的是这条路径的长度,所以要减1;
媛姐: 用一个数组count[N],每次count[下一个数]=count[当前数]+1;count[N]里放的是走到N时所用时间,所以走到下一步时,在他上一步位置地方所用时间加1即可。。。。。。。
媛姐计数方法很神奇,建议使用。。
媛姐代码:(比我的好多了,看着多舒服。。。建议学习啊,就是那个head和tail。。。。。)
#include#include #include int Q[300000]; int count[300000]; int sta[300000]; int n,head,tail; void Enq(int x) { Q[head++] = x; } int Deq(void) { return Q[tail++]; } int Qempty() { if( head == tail) return 1; return 0; } int main(void) { int N,K,temp,i; while(scanf("%d%d",&N,&K)!=EOF) { head = 0; tail = 0; memset(count,0,sizeof(count)); memset(Q,0,sizeof(Q)); memset(sta,0,sizeof(sta)); Enq(N); sta[N] = 1; while( !Qempty() ) { N = Deq(); if( N == K) { printf("%d\n",count[N]); break; } temp = N+1; if( temp<=100000 && sta[temp] == 0) { sta[temp] = 1; count[temp] = count[N] + 1; Enq(temp); } temp = N-1; if( temp>=0 && sta[temp] == 0) { sta[temp] = 1; count[temp] = count[N] + 1; Enq(temp); } temp = N*2; if( temp<=100000 && sta[temp] == 0) { sta[temp] = 1; count[temp] = count[N] + 1; Enq(temp); } } for(i=0;i
我的代码(本来队列用的是结构体,由于最初没发现错误在哪,改来改去就改成现在的样子了,唉,真难看):
#include#include #define N 100005int p[N],a[300000],rear;void In(int x){ a[rear++]=x;}int main(){ int x,y,i,k,count,t,temp1,temp2,front; scanf("%d%d",&x,&y); if(x>y) printf("%d\n",x-y); else { t=1; memset(p,0,sizeof(p)); front=rear=count=0; In(x); k=a[0]; p[x]=1; while(t) { temp1=front; temp2=rear; for(i=temp1;i =0&&p[k-1]==0) { if(k-1==y) { count++; t=0; break; } else { In(k-1); p[k-1]=1; } } if(2*k<=100000&&p[2*k]==0) { if(2*k==y) { count++; t=0; break; } if(!(k>y&&2*k>y)) { In(2*k); p[2*k]=1; } } } } } printf("%d\n",count-1); } return 0;}