Ёжик (3 уровень)

Условие:
План прямоугольного сада размером mxn состоит из квадратных зон. В каждой зоне растёт по дереву. С каждого дерева любой зоны могут упасть несколько яблок.
В левом верхнем квадратике находится ёжик, который должен дойти до правого нижнего квадратика. В саду существуют ограничения относительно способа передвижения: ёжик может двигаться из текущего квадратика только в один из двух соседних правый либо нижний.
Составьте программу, которая вычисляет максимальное количество яблок, которое может собрать ёжик, передвигаясь к нужному квадратику.

Технические условия:
План сада задан таблицей apples содержащей m строк и n столбиков. Элемент apples[i,j] таблицы указывает количество яблок, упавших с дерева в зону с координатами i,j.
Текстовый файл "input.txt" содержит в первой строке числа m,n разделённые пробелом. В каждой из следующих m строк содержится по n чисел apples[i,j] разделённых пробелами.
Файл "output.txt" должен содержать одно натуральное число.

Примеры файлов:

Решение 1: (by Andrei Bejenari [andrei.bejenari@wanadoo.fr])

---------- cut ----------
Классическая задача, которая решается в две строчки динамическим программированием (более того не требующего дополнительной памяти, что не так часто), решена рекурсией!!! Да, может для матрицы 10x10 back-tracking и пойдет, но а если она 100x100, то сколько лет понадобится опубликованному Вами алгоритму, чтобы закончить свою работу?
---------- cut ----------

const
    input = 'input.txt';
    output = 'output.txt';
    MaxN = 100;
var
    apples : array [0..MaxN,0..MaxN] of word;
    m,n,i,j : integer;
    fi,fo : text;

function max(a,b : word) : word;
begin
    if a>b then max:=a
    else max:=b
end;

begin
    assign(fi,input); reset(fi);
    assign(fo,output); rewrite(fo);

    readln(fi,m,n);
    for i:=1 to m do
    for j:=1 to n do read(fi,apples[i,j]);

    for i:=1 to m do
    for j:=1 to n do inc(apples[i,j],max(apples[i-1,j],apples[i,j-1]));

    writeln(fo,apples[m,n]);
    close(fi); close(fo);
end.

Решение 2: (by HellMan [alexec@newmail.ru])

---------- cut ----------
Почитал предлагаемое решение задачи про ежика... Тихий ужас ;)
Автор, наверное, не знаком с жесткими ограничениями, которые установлены на большинстве приличных олимпиад (т.е. выше городского уровня). Перебор - штука многофункциональная, но только при матрице скромных размеров. Потому что временнАя сложность алгоритма получается порядка 2^(m+n). Лучше будет применить динамическое программирование...
---------- cut ----------

{$A-,B-,D+,E-,F-,G-,I-,L+,N+,O-,P-,Q-,R-,S-,T-,V-,X-,Y+}
{$M 16384,0,655360}

var
    f: text;
    m, n, i, j, t, s: word;
    a: array[0..1, 0..5000] of longint;
begin
    assign(f, 'input.txt');
    reset(f);
    readln(f, m, n);
    s := n * 4 + 1; { sizeOf(longint) = 4 }
    fillChar(a[0], s, $00);
    fillChar(a[1], s, $00);
    for i := 1 to m do begin
    move(a[1], a[0], s);
    for j := 1 to n do
    begin
      read(f, t);
      if a[0, j] >= a[1, j - 1] then
      a[1, j] := a[0, j] + t
      else
        a[1, j] := a[1, j - 1] + t;
    end;
    readln(f);
    end;
    close(f);
    assign(f, 'output.txt');
    rewrite(f);
    writeln(f, a[1, n]);
    close(f);
end.