fork download
  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
stdin
14 15
stdout
2