У нас есть сетка размером Rx C, и она имеет ровно d ячеек, помеченных "D". Из этих d ячеек мы должны достичь ровно k ячеек (k <= d), чтобы расстояние, которое мы проходим, было минимальным. Начальная позиция - это ячейка (0,0); мы можем двигаться только вниз по сетке, хотя вы можете двигаться влево или вправо, как вам угодно. Следующее можно предположить, чтобы всегда быть истинным: начальная позиция никогда не отмечена с "D"; в каждой строке есть только одна буква «D», но в некоторой колонке может быть более одной буквы «D». Итак, если ячейка (0,4) помечена для перехода к ней из (0,0), мы проходим расстояние в 4 единицы. <strong>Например: предположим, что сетка имеет 5 строк и 5 столбцов с 3 "D", из которых вы должны достичь любого 2. Три "D" расположены в (1,4), (2, 3) и (4,4), как показано ниже. В этом случае ваш кратчайший маршрут состоит из 7 шагов и достижения «D» в строке 1 и строке 2. Взятие любой другой комбинации 2 «D» занимает 8 шагов, так что это минимально возможный.
