@stepan-neretin7

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

Есть некий массив
Или вот он на картинке, числа я отделил запятой 6028d91547715258285241.jpeg
Массив двухмерный
Игрок может ходить вправо и вверх
Начинает движение в нижней левой клетке, заканчивает в верхней правой.
Можно ли как-то красиво перебрать все варианты ходов из нижней левой до верхней правой чтобы уже выбрать тот вариант когда он соберет максиум, а когда миниум
Было бы круто понять как перебирать ходы в двухмерном пространстве
  • Вопрос задан
  • 69 просмотров
Пригласить эксперта
Ответы на вопрос 2
milssky
@milssky
Координатор племени фиолетовых обезьянок
О. Это 18 задача из ЕГЭ по информатике.
Исчерпывающее описание, алгоритмы и т.д. есть тут https://kpolyakov.spb.ru/download/ege18.doc
Ответ написан
wataru
@wataru
Разработчик на С++, гуглер, экс-олимпиадник.
Можно. Задача решается за O(n^2) динамическим программированием.

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

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

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
08 мар. 2021, в 12:35
50000 руб./за проект
08 мар. 2021, в 11:59
15000 руб./за проект
08 мар. 2021, в 11:19
15000 руб./за проект