Задача #65

Квадрат разлинован на NxN клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. На каждое перемещение Робот тратит 10% заряда батареи. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. В каждой клетке установлена зарядная станция, которая может повысить заряд робота не более, чем на число, указанное в соответствующей ячейке. Заряд робота не может превысить 100%. Если перед выполнением команд вправо или вниз процент зарядки батареи робота меньше 10%, то выполнение данных команд невозможно. В начальный момент уровень заряда равен значению, указанному в левой верхней клетке.

На зарядку на любого количества процентов робот тратит 5 минут, на выполнение команд вниз или вправо – 1 минуту.

Определите минимальное количество минут, за которое робот сможет преодолеть лабиринт – добраться до правой нижней клетки.

Исходные данные представляют собой электронную таблицу размером NxN, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщенными линиями.

Пример лабиринта

Для такого примера ответ будет: 16 (ВНИЗ-ВНИЗ-(Зарядка)-ВНИЗ-(Зарядка)-ВПРАВА-ВПРАВО-ВПРАВО)