
CAVE	Пещера CAVE Описание Гном Торин нашел план покинутой пещеры, в которой жил горный король Норус. На плане обозначено место, где находятся огромный клад. Горный король защитил свое богатство от искателей кладов, для чего расположил в пещере L каменных блоков, которые двигаются и могут раздавить искателя, и которые останавливаются, когда сокровища найдены. План задан в виде прямоугольной целочисленной матрицы MxN, элементами которой могут быть: -2 (клад) -1 (стена) 0 (пустое место) положительное число K (элемент K-го блока) K-й блок состоит из всех элементов, обозначенных числом K. Блок не обязательно связный, но все его элементы движутся синхронно. Нули в крайних строках или столбцах матрицы обозначают входы в пещеру. Отдельно указано начальное направление движения каждого блока (1 - вверх, 2 - направо, 3 - вниз, 4 - влево). Гном занимает клетку-вход. После этого он движется по таким правилам: на протяжении каждой секунды первым перемещается гном на пустую клетку из 4-х соседних (вверх, вниз, влево или направо) или остается на месте. Потом, на протяжении той же секунды, перемещается каждый блок на одну клетку (вверх, вниз, влево или направо): сначала первый, за ним второй и т.д. Если перед каким-нибудь элементом в направлении его движения находится стена, край пещеры, клад или другой блок, то на этом ходе блок не движется, а направление его движения изменяется на противоположное. Если блок во время движения попал в клетку с гномом, то гном гибнет. Задание Написать программу CAVE для поиска безопасного пути, который приведет к кладу за наименьшее время, считая, что такой путь существует. Входные данные Входной текстовый файл CAVE.DAT в первой строке содержит два числа M, N та L-количество блоков (3<=M<=75, 3<=N<=75, 0<=L<=1000). В следующих M строках содержаться N целых чисел - план пещеры. В следующих L строках заданы начальные направления их движения в порядке увеличения номеров. Выходные данные Выходной текстовый файл CAVE.SOL в первой строке должен содержать число K - время прохождения пути в секундах. В следующих K+1 строках - координаты положения гнома в каждую секунду (начиная с координат входа). Координаты должны быть заданы в порядке "строка столбец". Если существует несколько путей, достаточно указать один из них. Например: CAVE.DAT 4 5 1 -1 -1 -1 -1 -1 -1 0 1 0 -1 0 0 0 -2 -1 -1 -1 -1 -1 -1 1 CAVE.SOL 5 3 1 3 2 2 2 2 3 2 4 3 4

CAVE

Пещера
CAVE

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

План задан в виде прямоугольной целочисленной матрицы MxN, элементами которой могут быть:

-2 (клад)
-1 (стена)
0 (пустое место)
положительное число K (элемент K-го блока)

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

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

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

Входные данные
Входной текстовый файл CAVE.DAT в первой строке содержит два числа M, N та L-количество блоков (3<=M<=75, 3<=N<=75, 0<=L<=1000). В следующих M строках содержаться N целых чисел - план пещеры. В следующих L строках заданы начальные направления их движения в порядке увеличения номеров.

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

Например:

CAVE.DAT
4 5 1
-1 -1 -1 -1 -1
-1 0 1 0 -1
0 0 0 -2 -1
-1 -1 -1 -1 -1
1

CAVE.SOL
5
3 1
3 2
2 2
2 3
2 4
3 4