Задача 13.
Задана матрица натуральных чисел A(n,m). За каждый проход через клетку (i,j) взымается штраф A(i,j). Необходимо минимизировать штраф и
а) Пройти из какой-либо клетки 1-ой строки в n-ую строчку, при этом из текущей клетки можно перейти
1) в любую из 3-х соседних, стоящих в стpоке с номеpом на 1-цу большем;
2) в любую из 8 соседних клеток;
б) Реализовать пункт a) для перехода из клетки (1,1) в (n,m).
|
Решение задачи 13.
Для решения пункта 1 задачи достаточно воспользоваться
тем фактом, что для определения минимальной величины штрафа, взимаемого за проход в клетку i-той строки достаточно знать минимальные величины штрафа, взимаемого за проход в клетки (i-1)-той строки, которые являются соседними рассматриваемой клетке. Поэтому алгоритм решения пункта 1 следующий:
для i от 1 до n
Штраф[i,1]:=A[i,1] для i от 2 до n
для j от 1 до m
нц
Штраф[i,j]:=Штраф[i-1,j]+A[i,j];
если j>1 и Штраф[i,j] < Штраф[i-1,j-1]+A[i,j]; то Штраф[i,j]:=Штраф[i-1,j-1]+A[i,j];
если j<m и Штраф[i,j] < Штраф[i-1,j+1]+A[i,j]; то Штраф[i,j]:=Штраф[i-1,j+1]+A[i,j];
кц
Для решения пункта 2 можно воспользоваться алгоритмом Дейкстры нахождения минимального пути в графе из главы 'Графы'.
|
