|
Название задачи: Черепашка. |
 |
Условие
На квадратной доске расставлены целые неотрицательные числа. Черепашка, находящаяся в левом верхнем углу, мечтает попасть в правый нижний. При этом она может переползать только в клетку справа или снизу и хочет, чтобы сумма всех чисел, оказавшихся у нее на пути, была бы максимальной. Определить эту сумму.Формат входных данных
Первая строка — N — размер доски.
Далее следует N строк, каждая из которых содержит N целых чисел, представляющие доску.
Формат выходных данных
Одно число — максимальная сумма.
Решение
Эта задача является классикой динамического программирования. Ни одно печатное или электронное пособие по решению задач не обходится без разбора "Черепашки". Рассмотреть все возможные маршруты и просчитать их невозможно. Но можно свести задачу к аналогичной. Пусть нам известен "максимальный" путь для всех клеток, кроме правой нижней (функция F(X, Y)). Все нужные маршруты проходят через одну из клеток, смежных с этим углом (их всего две). Максимальный же маршрут проходит через ту клетку из двух, для которой значение функции F больше. Остается только правильно выполнить отсечение:
Function F(x,y:integer):longint; begin if B[x, y] = -1 then if F(x-1, y) > F(x, y - 1) then B[x, y] := F(x - 1, y) + A[x, y] else B[x, y] := F(x, y - 1) + A[x, y]; F := B[x, y] end;
Теперь необходимо подумать о граничных условиях. Логически правильнее было бы просчитать нашу функцию для левой и верхней границы. Это делается легко, так как для этих клеток существует только один маршрут (непосредственно вдоль границы). Но еще проще ввести в рассмотрение фиктивные нулевые строку и столбец и присвоить им нулевые значения. Действительно, эти клетки, в принципе, недостижимы, поэтому максимальная сумма равна нулю.
Итеративное заполнение массива также довольно просто. После введения граничных условий (любых из рассмотренных выше) дальнейшее заполнение осуществляется двойным циклом:
for i:=1 to N do for j:=1 to N do if B[i - 1, j] > B[i, j - 1] then B[i, j] := B[i - 1, j] + A[i, j] else B[i, j] := B[i, j - 1] + A[i, j];
