images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
26/04/2024 00:24:09

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

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

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

Ограничения: время – 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
loading