eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Пещера

Пещера

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Гном Торин нашел план покинутой пещеры, в которой жил горный король Норус. На плане обозначено место, где находится огромный клад. Горный король защитил свое богатство от искателей кладов, для чего расположил в пещере L каменных блоков, которые двигаются и могут раздавить искателя, и которые останавливаются, когда сокровища найдены.

План задан в виде прямоугольной целочисленной матрицы M×N, элементами которой могут быть: -2 (клад), -1 (стена), 0 (пустое место), положительное число K (элемент K–го блока). K–й блок состоит из всех элементов, обозначенных числом K. Блок не обязательно связный, но все его элементы движутся синхронно. Нули в крайних строках или столбцах матрицы обозначают входы в пещеру. Отдельно указано начальное направление движения каждого блока (1 – вверх, 2 – направо, 3 – вниз, 4 – влево).

Гном занимает клетку-вход. После этого он движется по таким правилам: на протяжении каждой секунды первым перемещается гном на пустую клетку из 4-х соседних (вверх, вниз, влево или направо) или остается на месте. Потом, на протяжении той же секунды, перемещается каждый блок на одну клетку (вверх, вниз, влево или направо): сначала первый, за ним второй и т.д. Если перед каким-нибудь элементом в направлении его движения находится стена, край пещеры, клад или другой блок, то на этом ходе блок не движется, а направление его движения изменяется на противоположное. Если блок во время движения попал в клетку с гномом, то гном гибнет.

Написать программу CAVE для поиска безопасного пути, который приведет к кладу за наименьшее время, считая, что такой путь существует.

Входные данные

Входной файл в первой строке содержит три числа M, N и L — количество блоков (3M75, 3N75, 0L1000). В следующих M строках содержаться N целых чисел — план пещеры. В следующих L строках заданы начальные направления их движения в порядке увеличения номеров.

Выходные данные

Выходной файл в первой строке должен содержать число K — время прохождения пути в секундах. В следующих K+1 строках — координаты положения гнома в каждую секунду (начиная с координат входа). Координаты должны быть заданы в порядке "строка столбец". Если существует несколько путей, достаточно указать один из них.

Пример

Входные данные #1
4 5 1
-1 -1 -1 -1 -1
-1 0 1 0 -1
0 0 0 -2 -1
-1 -1 -1 -1 -1
1
Выходные данные #1
5
3 1
3 2
2 2
2 3
2 4
3 4