题目链接:http://acm.xidian.edu.cn/problem.php?id=1313
bfs用队列模拟操作,剪枝最重要的就是标记,若该数已经在之前的层中到达,则没必要在新的层中做继续操作,并且可以用这个标记来记录层数;(这是一个技巧,可以记住以后用,我也是学的别人的)
用一个数组,A[n] = k,n即为达到的数,k为所在层数,下一次操作为A[m] = A[n] + 1;
1 #include<stdio.h> 2 #include<queue> 3 #include<memory.h> 4 using namespace std; 5 6 queue<int> Q; 7 int vis[100005]; 8 int n, m; 9 int bfs() 10 { 11 while(!Q.empty()) 12 { 13 int temp = Q.front(); 14 if(vis[temp + 1] == -1) 15 { 16 Q.push(temp + 1); 17 vis[temp + 1] = vis[temp] + 1; 18 if(temp + 1 == m) return vis[m]; 19 } 20 if(vis[temp - 1] == -1 && temp > 0) 21 { 22 Q.push(temp - 1); 23 vis[temp - 1] = vis[temp] + 1; 24 if(temp - 1 == m) return vis[m]; 25 } 26 if(temp * 2 <= 1e5 && vis[temp * 2] == -1 && temp > 0) 27 { 28 Q.push(temp * 2); 29 vis[temp * 2] = vis[temp] + 1; 30 if(temp *2 == m) return vis[m]; 31 } 32 Q.pop(); 33 } 34 } 35 36 37 int main() 38 { 39 while(scanf("%d %d",&n, &m) != EOF) 40 { 41 while(!Q.empty()) //清空队列很重要 42 Q.pop(); 43 memset(vis,-1,sizeof(vis)); 44 if(n >= m) 45 { 46 printf("%d ",n - m); 47 continue; 48 } 49 Q.push(n); 50 vis[n] = 0; 51 int result = bfs(); 52 printf("%d ",result); 53 } 54 return 0; 55 }