Задача на C

[mirawoo]

Друзья, помогите, пожалуйста, с такой задачкой:
Дана шахматная доска M*N с разными монетками на каждом квадрате.
Необходимо из стартовой левой нижней позиции перебраться вверх таким образом, что бы собрать наибольшую сумму монет.
По диагонали ходить нельзя. Можно только вправо и вверх
Прога не должна работать путем поиска самых больших ближайших чисел, так как самое большое число может находится
на другом конце матрицы.
Спасибо заранее.

[Sazary]

Раз двигаться можно только вправо и вверх, то, может, перебором?

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

[pu4koff]

Можно попробовать прикрутить алгоритмы поиска кратчайшего пути. волновой там или еще какой. Стоимость монетки - есть стоимость пути. Ну или, чтобы не превращать это в поиск самого длинного пути, стоимость пути = 100 - номинал монеты

[Somebody]

Может что-то типа

for (y = 0; y < n; y++)
	for (x = 0; x < m; x++)
		a[y][x] = max(a[y - 1][x], a[y][x - 1]);

В общем, выбор из клетки левее или ниже.

[pproger]

2Somebody неа, ибо ты ведь не знаешь, какие монетки будут дальше этого пути. на текущем шаге ты сделаешь выгодное решение, но на следующем может оказаться так, что выгоднее было пойти по другому пути
ну вот пример:

10 10 10 10 10
10 10 10 10 10
90 10 10 10 10
10 10 10 10 10
10 20 10 10 10

идем из левого нижнего угла. на первом же ходу твой алгоритм даст сбой

[Somebody]

Ой, там имелось в виду +=. В каждом элементе будет наибольшая возможная сумма по пути до него, тогда для каждой клетки надо только выбрать предыдущую. В общем, типа:

int m, n;
scanf("%d %d", &m, &n);
int a[99][99];
char prev[99][99];
int x, y;
for (x = 0; x < m; x++)
	a[0][x] = 0;
for (y = n; y > 0; y--)
	for (x = 1; x <= m; x++)
	{
		a[y][0] = 0;
		scanf("%d", &a[y][x]);
	}
for (y = 1; y <= n; y++)
	for (x = 1; x <= m; x++)
     if (a[y - 1][x] > a[y][x - 1])
			a[y][x] += a[y - 1][x], prev[y][x] = 'y';
		else
			a[y][x] += a[y][x - 1], prev[y][x] = 'x';
char path[m + n - 1];
path[sizeof(path)/sizeof(path[0]) - 1] = 0;
x = m, y = n;
for (int i = m + n - 3; i >= 0; i--)
	path[i] = prev[y][x] == 'y' ? (y--, '^') : (x--, '>');
puts(path);