Подразделы

Другие разделы

Дата и время

22/11/2024 00:08:24

Авторизация

Лето 9

A. Результаты квалификации B. Развлечение с калькулятором C. Скорость воробьев D. Соединительная линия E. Самый острый угол F. Однокоренные слова G. Дробь в LATeX-е H. Brownie Points I I. Magic Bitstrings J. Brownie Points II

D. Соединительная линия

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

На плоскости, разделённой на клетки, заданы два прямоугольника с координатами `(x_1,\ y_1)-(u_1,\ v_1)`, `(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