printРабочее место участника

printЗадачи

1509. Очистка озера

Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (1) idea

Для очистки загрязненного озера было решено использовать подводного робота. С помощью подводной съемки было выяснено местонахождение всех препятствий и загрязнений в озере и составлена карта. Озеро было разбито на квадратные участки-клетки, в каждой клетке было обнаружено от 0 до 9 единиц мусора. Робот может передвигаться по дну озера, обходя препятствия вокруг, но не может их "перелететь" сверху. За одну единицу времени робот может переместиться в соседнюю клетку по вертикали или горизонтали. Робот может мгновенно поднять манипуляторами любой предмет, находящийся в той же клетке, где находится робот. Также мгновенно он может бросить предмет в манипуляторах на грунт в этой клетке. При перемещении робот может нести не более одного предмета. Робот должен собрать весь мусор в определенной клетке озера, с которой мусор будет поднят на поверхность и вывезен на свалку. После выполнения работы роботу не обязательно находиться в клетке с подъемником. Робот может быть как в этой клетке, так и в любой другой.
Напишите программу, определяющую количество мусора, от которого можно будет очистить озеро, и минимальное время, которое потребуется для выполнения этой работы.
Первая строка ввода содержит шесть целых чисел - размеры озера в клетках `N` и `M` (`2\ ≤\ N,\ M\ ≤\ 100`), начальное расположение робота `R` и `C` (`1\ ≤\ R\ ≤\ N`, `1\ ≤\ C\ ≤\ M`) и расположение подъемника `D` и `E` (`1\ ≤\ D\ ≤\ N`, `1\ ≤\ E\ ≤\ M`). Далее следует `N` строк по `M` символов – карта озера. Символ '#' означает клетку с препятствием (например, скалы или водоросли), а цифры от 0 до 9 означают количество единиц мусора в свободной от препятствий клетке. Клетки с роботом и подъемником не содержат препятствий.
Вывести два целых числа – максимальное количество единиц мусора, которое можно будет поднять на поверхность озера из клетки с подъемником, и минимальное время, которое потребуется роботу для выполнения этой работы.

Пример ввода

2 3 2 3 1 3
1#3
#12

Пример вывода

6 7
loading