Помогите написать программу для определения оптимального пути (возможно псевдокод)

[nastr]

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

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

Примеры файлов:
Input.txt Output.txt
3 3
1 2 3
1 2 3
1 2 3 12

[XPEHOMETP]

Боюсь, что в реале ёжик рано или поздно долбанется башкой о ствол яблони, положение которого не учтено в условии...

[AMDBulldozer]

#include <stdio.h>

int n=3, m=3;
int a[][3] = {
{1, 2, 3},
{1, 2, 3},
{1, 2, 3}
};

int MaxApples(i0,j0){
int i, i1, max=0, max0, sum=0;
if( j0 >= m ) {
for(i=i0;i<=n;i++) sum+=a[i-1][m-1];
return sum;
} else {
for(i1=i0;i1<=n;i1++){
sum=0;
for(i=i0;i<=i1;i++) sum+=a[i-1][j0-1];
max0=sum+MaxApples(i1,j0+1);
if( max0 > max ) max=max0;
}
return max;
}
}

int main(){
printf("Maximum number of apples = %d\n", MaxApples(1,1));
}
(Чтение файла я не делал - только рекурсию)

[nastr]

почему не получается инициализировать массив следующим образом:
int[][] apples = new int[4][] { { 3, 3 }, { 1, 2, 3 }, { 1, 2, 3 }, { 1, 2, 3 } };

[AMDBulldozer]

nastr, потому что то, что Вы написали, это вообще не массив.

[nastr]

AMDBulldozer »
Огромное спасибо, то что нужно!
Я модифицировал под C#:
int n = 3, m = 3;
int[,] apple = new int[3,3] { { 1, 2, 3 }, { 1, 2, 3 }, { 1, 2, 3 } };

int MaxApples(int i0, int j0)
{
int i, i1, max = 0, max0, sum = 0;
if (j0 >= m)
{
for (i = i0; i <= n; i++)
sum += apple[i - 1, m - 1];
return sum;
}
else
{
for (i1 = i0; i1 <= n; i1++)
{
sum = 0;
for (i = i0; i <= i1; i++)
sum += apple[i - 1, j0 - 1];
max0 = sum + MaxApples(i1, j0 + 1);
if (max0 > max) max = max0;
}
return max;
}
}

[pva]

Типовая задача динамического программирования, решается за один проход M*N (рекурсия не нужна).
http://ru.wikipedia.org/wiki/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1 %80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5

очень походит на нечёткое сравнение
http://habrahabr.ru/post/114997/