Как перебрать ходы в двухмерном пространстве?

Question

[stepan-neretin7]

Есть некий массив
Или вот он на картинке, числа я отделил запятой
Массив двухмерный
Игрок может ходить вправо и вверх
Начинает движение в нижней левой клетке, заканчивает в верхней правой.
Можно ли как-то красиво перебрать все варианты ходов из нижней левой до верхней правой чтобы уже выбрать тот вариант когда он соберет максиум, а когда миниум
Было бы круто понять как перебирать ходы в двухмерном пространстве

Comments

[Сергей Соколов]

вроде бы тут 13x13 – стороны нечетные, значит, для максимума можно тупо змейкой обойти весь массив!
Вопрос можно закрывать )

[Алан Гибизов]

См.п.3.8

[stepan-neretin7]

Алан Гибизов, я не код заливаю в виде изображения, а всего лишь в удобном виде двухмерное поле показываю

[Алан Гибизов]

stepan-neretin7, во-первых, надо делать не как тебе удобно, а как удобно тем, кто отвечает на твои вопросы. А как удобно им, сказано в правилах;
Во-вторых, если у тебя тут нет кода, то зачем ставить тег python? См.п.3.1
Десяткам тысяч читателей тега Python совершенно ни к чему этот вопрос.

Answer 1

[milssky]

О. Это 18 задача из ЕГЭ по информатике.
Исчерпывающее описание, алгоритмы и т.д. есть тут https://kpolyakov.spb.ru/download/ege18.doc

Comments

[stepan-neretin7]

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

Answer 2

[Wataru]

Можно. Задача решается за O(n^2) динамическим программированием.

Считайте F(x,y) - лучшую возможную сумму, чтобы закончить в ячейке (x, y).

База: в левом нижнем углу ответ - число в этой ячейке; за границами - ответ минус бесконечно плохое число (плюс бесконечность, если ищем минимум, например).

Пересчет F(x,y) = a[x,y] + min(F(x+1,y), F(x,y-1)) - выбираем, с какой стороны выгоднее прийти в эту ячейку.