Соединительная линия
Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
На плоскости, разделённой на клетки,
заданы два прямоугольника с координатами
(x1, , (x_2,\ y_2)-(u_2,\ v_2) и две различные точки
с координатами (x_s,\ y_s) и (x_d,\ y_d). Требуется:
- найти кратчайший путь между указанными точками, переходящий от клетки к клетке по вертикали или горизонтали и не пересекающий прямоугольники;
- вывести изображение прямоугольников и кратчайшего пути.
При этом пустая клетка должна изображаться символом '.',
клетка, принадлежащая прямоугольнику – символом '#',
начальная и конечная точки – символом '*',
клетка, через которую путь проходит по горизонтали – символом '-',
клетка, через которую путь проходит по вертикали – символом '|',
клетка, в которой путь делает поворот – символом '+'.
Изображение должно быть прямоугольником минимального размера,
достаточного, чтобы вместить все непустые клетки.
Ось ординат должна быть направлена снизу вверх.
Ввод
Во входном файле содержатся целые числа
x_1\ y_1\ u_1\ v_1\ x_2\ y_2\ u_2\ v_2\ x_s\ y_s\ x_d\ y_d.
Вывод
В выходном файле должно содержаться изображение, выведенное построчно.
Если решений несколько, выведите любое из них.
Ограничения
1\ ≤\ x_i,\ y_i,\ u_i,\ v_i\ ≤\ 100,
Прямоугольники могут пересекаться.
Начальная и конечная точки не лежат внутри прямоугольников.
Пример ввода 1
2 3 7 5 6 7 8 8 6 2 5 9
Пример вывода 1
...*...
...|###
...|###
...+--+
######|
######|
######|
....*-+
Пример ввода 2
2 3 7 6 8 7 6 8 6 2 5 9
Пример вывода 2
...*---+
....###|
....###|
######++
######|.
######|.
######|.
....*-+.
Источник: А. Кленин, ДВГУ, Весенний турнир, 2008