<PREV Problem:
NEXT>
Solved by 172 users: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Лабиринт

Time limit = 1 second(s)

Необходимо найти кратчайший путь выхода из лабиринта. Лабиринт представляет собой прямоугольник размером N х M, со всех сторон окружённый стенами, и состоящий из квадратных клеток размера 1 x 1. Лабиринт снабжен K выходами, до одного из которых необходимо добраться. В некоторых клетках лабиринта находятся стены. Можно перемещаться из клетки в любую из четырех соседних с ней, если в той клетке, куда вы хотите переместиться, нет стены. Кроме того, лабиринт снабжён системой гипертуннелей, способных перемещать из одной клетки лабиринта (вход в гипертуннель) в другую (выход из гипертуннеля). Когда вы находитесь в клетке, где есть вход в гипертуннель, вы можете (но не обязаны) им воспользоваться. Начальное положение известно. Вам необходимо найти кратчайший путь (то есть путь, проходящий через минимальное количество клеток) до любого из выходов.

Input. В первой строке входного файла записаны числа N и M (2 ≤ N ≤ 1000, 2 ≤ M ≤ 1000), задающие размеры лабиринта: N — количество строк в плане лабиринта, M — количество столбцов. Во второй строке записаны начальные координаты XA, YA (1 ≤ XAN, 1 ≤ YAM). Первая координата задает номер строки, вторая — номер столбца. Строки нумеруются сверху вниз, столбцы слева направо. Далее следуют N строк по M чисел, задающих описание стен внутри лабиринта: 1 соответствует стенке, 0 — её отсутствию. Далее в отдельной строке записано число H (0 ≤ H ≤ 1000) — количество гипертуннелей. В последующих H строках идут описания гипертуннелей. Каждый гипертуннель задается 4 числами: X1, Y1, X2, Y2 (1 ≤ X1, X2N; 1 ≤ Y1, Y2M) — координатами входа и выхода гипертуннеля. Никакие два гипертуннеля не имеют общего входа. После этого в отдельной строке следует число K (1 ≤ K ≤ 10) — количество выходов из лабиринта. В последующих K строках идут описания выходов из лабиринта. Каждый выход задается двумя координатами X и Y (1 ≤ XN; 1 ≤ YM). Гарантируется, что начальные координаты не совпадают ни с одним из выходов и он не стоит в клетке, занятой стеной. Никакие входы и выходы гипертуннелей, а также выходы из лабиринта не находятся в клетках, занятых стенами. Никакой вход в гипертуннель не совпадает с выходом из лабиринта.

Output. Если выход невозможен, выведите единственную строку с надписью "Impossible". В противном случае в первой строке выведите число L — количество клеток в кратчайшем пути выхода. В последующих L строках последовательно выведите координаты клеток кратчайшего пути выхода. Если решений несколько, то выведите любое из них.

Input#1
4 5
2 1
0 0 0 0 0 
0 1 0 0 0 
0 0 0 0 0 
0 0 0 0 0 
2
1 2 1 4
3 1 1 4
1
2 4
Output#1
4
2 1
3 1
1 4
2 4

Input#2
3 3
1 1
0 1 0
0 1 0
0 1 0
0
1
3 3
Output#2
Impossible

Author:
Известная задача. Описание, тесты, чекер -- Денис Чернилевский
2 декабря 2006

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 210ms

SW soft NIX
ID = 54.161.108.158