Решение: Максимальная и минимальная суммы
Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). Исполнитель Робот начинает движение из левой верхней клетки и может перемещаться только вправо или вниз. Между соседними клетками могут находиться внутренние стены, сквозь которые Робот пройти не может. В каждой клетке лежит монета достоинством от 1 до 100; посетив клетку, Робот забирает монету. В клетках, которые справа и снизу ограничены стенами, движение заканчивается, а накопленная сумма считается итоговой. Определите максимальную и минимальную суммы среди всех возможных маршрутов от левой верхней клетки до конечной клетки. Исходные данные находятся в прилагаемом файле электронной таблицы: значения клеток и внутренние стены обозначены в таблице.
Решение по шагам
5 шаговСначала считываем из файла стоимость монет в каждой клетке и наличие стен между соседними клетками.
Для каждой клетки храним два значения: максимальную и минимальную сумму, которую можно получить при попадании в эту клетку из левой верхней клетки.
Если в клетку можно попасть сверху, учитываем значения верхней клетки. Если можно попасть слева, учитываем значения левой клетки. К выбранному значению прибавляем стоимость монеты текущей клетки.
$$M_{i,j}=a_{i,j}+\max(M_{i-1,j},M_{i,j-1}),\quad m_{i,j}=a_{i,j}+\min(m_{i-1,j},m_{i,j-1})$$Для переходов, закрытых стеной, соответствующий источник не учитывается. В начальной клетке обе суммы равны стоимости её монеты.
На всех клетках, ограниченных стенами справа и снизу, выбираем максимальное и минимальное из рассчитанных значений.
Точный числовой ответ невозможно определить без содержимого прилагаемой электронной таблицы.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Учитывают только правую нижнюю клетку и игнорируют другие конечные клетки.
Проходят через внутреннюю стену.
Не добавляют стоимость монеты начальной или конечной клетки.
Для всех клеток используют только максимум или только минимум вместо одновременного вычисления обоих значений.