столбец сформированы}
for j:=2 to n do
if S[i-1,j]>S[i,j-1] then S[i,j]:=A[i,j]+S[i-1,j] else S[i,j]:=A[i,j]+S[i,j-1];
Итак, мы получаем матрицу:
1 3 7 7 12 15
4 12 21 28 34 43
8 19 29 38 42 52
8 25 29 43 50 61
10 30 36 44 58 66
15 39 47 47 64 69
Максимально возможная сумма маршрута(SS) получена - 69. Осталось найти сам маршрут. Начинаем с последней клетки [N,N]. Это конечная клетка маршрута. Уменьшаем значение SS на значение А[N,N] и ищем соседнюю клетку с суммой 66 - это будет предпоследняя клетка маршрута. Продолжаем процесс до тех пор, пока не дойдем до клетки (1,1). Маршрут найден.
о93_3 Первый способ решения. Соединим каждую точку с каждым отрезком прямой цвета q1. Среди этих отрезков уже есть и искомая дорога, образованная совокупностью каких-то отрезков. Остается выделить ее. Закрасим область вне города цветом q2 до цвета отрезков q1. Если сейчас найти точку внутри области и закрасить внутреннюю область цветом q3 до цвета q2, то граница между двумя цветами q2 и q3
