fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <queue>
  4. #include <vector>
  5. #include <iostream>
  6.  
  7. using namespace std;
  8.  
  9. int sum_n (int n){ //подсчёт суммы цифер в числе
  10. 	int res = n/1000 + (n%1000-n%100)/100 + (n%100-n%10)/10 + n%10;
  11. 	return res;
  12. }
  13.  
  14. bool was [10000]; //массив использованных вершин.
  15. int vertex[10000]; //подсчёт кол-ва пройденных рёбер..
  16. queue<int> q; //очередь для BFS
  17.  
  18. //BFS
  19. void bfs (int start, int finish){
  20. 	if (start==finish){  //если мы сразу попали в нужную вершину - выходим из программы.
  21. 		cout << 0 << endl;
  22. 		return;
  23. 	}
  24. 	else {
  25. 		for (int i=0; i<10000; i++){ //предположим, что расстояние до любой вершины = 1
  26. 			vertex[i]=1;
  27. 		}
  28. 		q.push (start); //будем рассматривать каждую вершину
  29. 		was[start] = true;
  30. 		while (!q.empty()){
  31. 			int tmp = q.front(); //рассматриваемая вершина
  32. 			q.pop();
  33. 			int tmp1 = tmp;
  34. 			tmp1 *= 3; //"ребёнок" рассматриваемой вершины, со значением родителбской вершины *3.
  35. 			if (!was[tmp1]){
  36. 				if (tmp1 == finish){//если финиш, то выводим длину пути до вершины.
  37. 					cout << vertex[tmp] << endl;
  38. 					return;
  39. 				}
  40. 				else if (tmp1 < 10000 && tmp1>=0){
  41. 					was[tmp1] = true;//иначе помечаем вершину, как пройденную и засовываем её в очередь на рассмотрение
  42. 					q.push(tmp1);
  43. 					vertex[tmp1]=vertex[tmp]+1;//и прибавляем 1 к длине пути.
  44. 				}
  45. 			}
  46. 			//действия повторяются для других операций.
  47. 			tmp1=tmp;
  48. 			tmp1 += sum_n(tmp1);
  49. 			if (!was[tmp1]){
  50. 				if (tmp1 == finish){
  51. 					cout << vertex[tmp] << endl;
  52. 					return;
  53. 				}
  54. 				else if (tmp1 < 10000 && tmp1>=0){
  55. 					was[tmp1] = true;
  56. 					vertex[tmp1]=vertex[tmp]+1;
  57. 					q.push(tmp1);
  58. 				}
  59. 			}
  60. 			tmp1=tmp;
  61. 			tmp1 -= 2;
  62. 			if (!was[tmp1]){
  63. 				if (tmp1 == finish){
  64. 					cout << vertex[tmp] << endl;
  65. 					return;
  66. 				}
  67. 				else if (tmp1 < 10000 && tmp1>=0){
  68. 					was[tmp1] = true;
  69. 					vertex[tmp1]=vertex[tmp]+1;
  70. 					q.push(tmp1);
  71. 				}
  72. 			}
  73. 		}
  74. 	}
  75. }
  76.  
  77. int main() {
  78. 	int a, b;
  79. 	cin >> a >> b; //ввод начала и конца
  80. 	bfs (a, b);//процедура выполнения
  81. 	return 0;
  82. }
  83.  
Success #stdin #stdout 0s 3284KB
comments (?)
stdin
copy 
14 15
stdout
copy 
2
https://ideone.com/XsdUzV
Шайтан-машинка
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!