Найти лучший способ добраться из координаты 0,0 до левого нижнего угла в матрице N на M?

Question

[mmerkulov0]

Дана матрица размером n на m, где в каждой ячейке указано значение. Можно двигаться либо вниз либо направо. Как добраться из координаты 0,0 в конец (n-1,m-1, нумерация с 0) собрав при этом максимальное/минимальное количество значений?

Comments

[dmshar]

От исходной матрицы переходите к матрице разрешенных путей. Она у вас не такая уж и большая, потому как из всех клеток исходят только два пути: вниз и вправо. А из самых нижних и самых правых - вообще по одному.
Вес ребра равен ""значению" той ячейки, в которую это ребро приходит.
Все, задача сведена к известной задачи поиска самого короткого (ну или длинного, тогда надо немного изменить веса) пути на графе. Надеюсь эту задачу вы знаете как решать.

Answer 1

[Матвей Полубрюхов]

Для каждого шага необходимо выбирать лучший вариант между вариантами вниз и направо. Т.е. сравнивать числа снизу и справа и выбирать наибольшее/наименьшее. Это ПОЧТИ всегда даёт правильный ответ (может давать ошибочный ответ, если числа снизу и справа равны).