Максимальный путь,Лабиринт.

[Тамерлан Абилов]

В индийском храме пол прямоугольной формы выложен одинаковыми квадратными плитками 1х1, на каждую из которых высыпано от 0 до k зернышек (k ≤ 30000). Размеры пола mхn. Мышка выбегает из левого нижнего угла пола храма и двигается к входу в другую норку, расположенную в противоположном углу. Мышка может двигаться только вправо или вперед, собирая все зернышки с плитки, на которой она находится.

Найти маршрут, двигаясь по которому мышка соберет наибольшее количество зернышек.

public static int path(int i,int j){

	//	if ((i==-1) || (j==17)) return 0; вне лабиринта....
		
		//System.out.println(a[i,j]);
		return Math.max(a[i][j]+path(i-1,j),a[i][j]+path(i,j+1));
	}

Ребята,помогите с алгоритмом пожалуйста.кроме самого маршрута хочется максимальный путь найти)но выше размера матрицы 15*15 например (пока учитываю только квадратную..) уже понятно ,что долго работать будет)а отсечь пути ещё на задаче минимального пути я мог бы, пусть и не такой рекурсией.но что делать в этом случае?)можете подсказать?

[Аватар]

Мышка может двигаться только вправо или вперед

вперед нужно понимать вверх?

Тогда не понял насчет минимального и максимального пути. При данных условия длина любого маршрута = m+n-1

[BDA]

*delete 10 letters*

[Тамерлан Абилов]

Да я реализовал точно так же как написано левый нижний угол)вперед это вверх)
запускаю path(maxİ-1,0)...

[Тамерлан Абилов]

	for (int i=0;i<17;i++){    //массив 17*17..
				System.out.println();
				for (int j=0;j<17;j++) {
				a[i][j]=rn.nextInt(10); //rn-Random.
				System.out.print(" "+a[i][j]);
				}
			 }
			
                   System.out.println("sum="+path(16,0));

[Тамерлан Абилов]

BDA,всмысле?)

[Тамерлан Абилов]

Решить в виде задачи в графе можно(без рекурсии). структура есть.но динамически как можно это сделать?Ибо классификация такая.
Информация о задаче
Лимит времени: 1 секунда
Лимит памяти: 64 MB
Баллы за пройденный тест: 8.33333
Сложность: 39% 360/590
Автор: Анатолий Присяжнюк
Классификация: Динамическое программирование

[Serge_Bliznykov]

Тамерлан Абилов, это классическая задача на динамическое программирование. Возьмите ЛЮБОЙ учебник по ДП и там обязательно будет разбор этой задачи.

Задача эта и на форуме неоднократно решалась.
например,
http://www.programmersforum.ru/showthread.php?t=70592 (особенно пост #6)

http://www.programmersforum.ru/showthread.php?t=82696

http://www.programmersforum.ru/showthread.php?t=65954
http://programmersforum.ru/showthread.php?t=60512
http://www.programmersforum.ru/showthread.php?t=60880


да и суть решения в том, что заводим двухмерный массив и в него прописываем значения от обратного - т.е. двигаясь от финиша к началу, в каждую клетку записываем максимальное значение, которое может быть получено в данной клетке..

[Тамерлан Абилов]

Сергей,спасибо большое)

[Serge_Bliznykov]

Не за что!
Успехов в решении!