fork download
copy 
  1. #include <iostream>
  2. #include <ctime>
  3. using namespace std;
  4.  
  5. int N;
  6.  
  7. int min_3(int a, int b, int c) // Возвращает минимальное из 3-х элементов.
  8. {
  9. 	int min;
  10. 	if ((a<b) && (a<c)) min = a;
  11. 		else if (b<c) min = b;
  12. 			else min = c;
  13. 	return min; 
  14. }
  15.  
  16. int ind_min_3(int a, int b, int c) // Возвращает индекс минимального из 3-х элементов. Если a - минимальное, то 1; если b, то 2; если c, то 3.
  17. {
  18. 	int ind;
  19. 	if ((a<b) && (a<c)) ind = 1;
  20. 		else if (b<c) ind = 2;
  21. 			else ind = 3;
  22. 	return ind;
  23. }
  24.  
  25. void build_path(int ** Arr, int i, int j) // Ф-ция построения пути.
  26. {
  27. 	cout << "["<<i<<","<<j<<"] "; // Выводим индекс элемента.
  28. 	if (i==0 && j==0)
  29. 		return; // Выходим, если оказались в начале пути.
  30.  
  31. 	int k; // Переменная для определения движения.
  32. 	if (i>0 && j>0)
  33. 		k = ind_min_3(Arr[i-1][j],Arr[i][j-1],Arr[i-1][j-1]); // Ищем индекс минимального из элементов на 1 выше, на 1 левее, и на 1 выше по диагонали
  34. 															  // среди элементов с индексами i>0 и j>0 для определения направления движения.
  35.  
  36. 	if (i>0 && j==0) // Если находимся в нулевой строке, то двигаемся только влево.
  37. 		k = 1; 
  38. 	if (i==0 && j>0) // Если находимся в нулевом столбце, то двигаемся только вверх.
  39. 		k = 2;
  40.  
  41. 	switch (k) // Выбираем куда двигаться.
  42. 	{
  43. 		case 1: 
  44. 			build_path(Arr, i-1,j);
  45. 			break;
  46. 		case 2:
  47. 			build_path(Arr, i,j-1);
  48. 			break;
  49. 		case 3:
  50. 			build_path(Arr, i-1,j-1);
  51. 			break;
  52. 	}
  53.  
  54.  
  55. }
  56.  
  57. int main() {
  58.  
  59. 	srand(time(0)); // Генерация случайных чисел.
  60.  
  61. 	cin >> N; // Считываем количество элементов в матрице. (NxN)
  62.  
  63. 	int **A = new int * [N]; // Объявляем динамический массив А.
  64. 	int **B = new int * [N]; // Объявляем динамический массив B.
  65. 	for (int i = 0; i < N; i++) {
  66.     	A[i] = new int[N]; 
  67.     	B[i] = new int[N];
  68. 	}
  69.  
  70. 	for (int i=0; i<N; i++) // Заполняем матрицу A случайными значениями.
  71. 		for (int j=0; j<N; j++){
  72. 			if ((i==0)&&(j==0)) A[i][j]=0; // Элемент с индексом [0,0] всегда равен 0.
  73. 			else
  74. 				A[i][j]=rand() % 10;
  75. 			B[i][j]=0;
  76. 		}
  77.  
  78. 	cout << "Сгенерированный массив:" << endl; 
  79. 	for (int i=0; i<N; i++){ // Вывод матрицы A.
  80. 		for (int j=0; j<N; j++){
  81. 			cout << A[i][j] << " ";
  82. 		}
  83. 		cout << endl;
  84. 	}
  85.  
  86. 	cout << "---" << endl;
  87.  
  88.  
  89. 	cout << "Массив стоимости путей:"<< endl;
  90. 	for (int i=0; i<N; i++) // Заполняем матрицу стоимостей B.
  91. 		for (int j=0; j<N; j++)
  92. 			{
  93. 				if (i==0 && j==0)
  94. 					B[i][j] = 0; // Для элемента с индексами [0,0] стомость в B равна 0.
  95. 				else
  96. 				{
  97. 					if (i==0)
  98. 					{
  99. 						B[i][j]=B[i][j-1]+A[i][j];	// Для всех элементов из 0-й строки стомость равна сумме стоимости из матрицы A и стоимости пути на предыдущем шаге (из B).
  100. 					}
  101. 					else
  102. 					{
  103. 						if (j==0)
  104. 						{
  105. 					    	B[i][j]=B[i-1][j]+A[i][j]; // Для всех элементов из 0-го столбца стомость равна сумме стоимости из матрицы A и стоимости пути на предыдущем шаге (из B).
  106. 						} else
  107. 							B[i][j]=A[i][j]+min_3(B[i-1][j],B[i][j-1],B[i-1][j-1]); // Иначе (i>0, j>0) стоимость равна сумме стоимости из A и минимальному из 
  108. 																					// стоимостей в B выше на 1 строку, или левее на 1 столбец, или выше на
  109. 																					// 1 строку и левее на 1 столбец (выше по диагонали).
  110. 					}
  111. 				}
  112. 			}
  113.  
  114. 	for (int i=0; i<N; i++){ // Распечатываем матрицу стоимостей B.
  115. 		for (int j=0; j<N; j++){
  116. 			cout << B[i][j] << " ";
  117. 		}
  118. 		cout << endl;
  119. 	}
  120.  
  121.  
  122. 	cout << endl << "Маршрут (в обратном порядке):" << endl;
  123. 		build_path(B, N-1, N-1); // Восстанавливаем маршрут рекурсивно. Параметры: массив, индексы элемента, с которого начинаем восстанавливать.
  124. 	cout << endl;
  125.  
  126.  
  127. 	return 0;
  128. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
4
stdout
copy 
Сгенерированный массив:
0 1 1 1 
4 4 3 4 
3 8 9 6 
1 2 2 5 
---
Массив стоимости путей:
0 1 2 3 
4 4 4 6 
7 12 13 10 
8 9 11 15 

Маршрут (в обратном порядке):
[3,3] [2,3] [1,2] [0,1] [0,0]
https://ideone.com/vY39VT
language:
C++ (gcc 8.3)
created:
5 years 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!