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

printЗадачи

2236. Матрица в многомерном пространстве

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

В некотором многомерном подпространстве путешествует невырожденная матрица размера 3x3, двигаясь только вертикально или горизонтально. Она должна найти путь к выходу из подпространства, который всегда существует. В случае, если матрица встречает препятствие, которое не может обойти в полном виде, то она может сжаться до одного единственного собственного значения и продолжить весь оставшийся путь в таком виде. Матрица сжимается относительно центральной клетки, после сжатия размер матрицы становится 1x1. В сжатом виде шаги матрицы становятся медленнее в 9 раз. Сжатие матрицы происходит мгновенно, то есть без затрат времени. Необходимо определить наименьшее время, необходимое для выхода из подпространства.
В первой строке ввода содержится 6 целочисленных значений, разделенных пробелами: координаты `X`, `Y` начального положения центральной ячейки матрицы, координаты `X`, `Y` выхода из подпространства (все координаты вычисляют с 0, начало координат находится в левом верхнем углу), ширина `W` и высота `H` подпространства (`3\ ≤\ H,\ W\ ≤\ 200`). В следующих `H` строчках описывается карта подпространства: символу '.' соответствует свободная клетка подпространства, символу '#' соответствует преграда. В начальной положении препятствий в соседних с центром матрицы клетках нет.
Вывести одно целое число – минимальное время для выхода матрицы из подпространства. Для выхода из подпространства центр матрицы должен оказаться в клетке, соответствующей выходу. Один шаг матрицы в несжатом виде занимает 1 единицу времени, один шаг в сжатом виде – 9 единиц времени.

Пример ввода

1 5 10 5 11 11
###........
##....#....
#..........
......##...
.....##....
....##.....
.....##....
......##...
#......##..
##......##.
###......##

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

87
Пояснение к примеру:
32123.png
На рисунке символами 'X' отмечен путь перемещения центра матрицы в несжатом виде, а символами '*' – путь перемещения матрицы в сжатом виде.
loading