fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <algorithm>
  5. using namespace std;
  6. int used[10000];
  7. vector<int> par, dist;
  8. void bfs(int v){
  9. 	used[v]=1;
  10. 	dist[v]=0;
  11. 	queue<int> q;
  12. 	q.push(v);
  13. 	while(!q.empty()){
  14. 		int x=q.front();
  15. 		q.pop();
  16. 		int y;
  17. 		if(x<9000){
  18. 			y=x+1000;
  19. 			if(used[y]==0){
  20. 			q.push(y);
  21. 			used[y]=1;
  22. 			dist[y]=dist[x]+1;
  23. 			par[y]=x;
  24. 		}
  25. 	}
  26. 	if(x%10!=1){
  27. 		y=x-1;
  28. 		if(used[y]==0){
  29. 			q.push(y);
  30. 			used[y]=1;
  31. 			dist[y]=dist[x]+1;
  32. 			par[y]=x;
  33. 		}
  34. 	}
  35. 	y=(x%1000)*10+x/1000;
  36. 	if(used[y]==0){
  37. 		q.push(y);
  38. 		used[y]=1;
  39. 		dist[y]=dist[x]+1;
  40. 		par[y]=x;
  41. 	}
  42. 	y=x/10+(x%10)*1000;
  43. 	if(used[y]==0){
  44. 		q.push(y);
  45. 		used[y]=1;
  46. 		dist[y]=dist[x]+1;
  47. 		par[y]=x;
  48. 		}
  49. 	}
  50. }
  51. int main(){
  52. 	int a,b;
  53. 	cin>>a>>b;
  54. 	par.assign(10000,-1);
  55. 	dist.assign(10000,-1);
  56. 	bfs(a);
  57. 	vector<int>ans;
  58. 	ans.push_back(b);
  59. 	while(par[b]!=-1){
  60. 		b=par[b];
  61. 		ans.push_back(b);
  62.  
  63. 	}
  64. 	reverse(ans.begin(), ans.end());
  65. 	for(int x:ans){
  66. 		cout<<x<<endl;
  67. 	}
  68. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
1234
4321
stdout
copy 
1234
2234
3234
4323
4322
4321
https://ideone.com/fm2u53
language:
C++14 (gcc 8.3)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!