В подземном бункере укрылись террористы. Бункер имеет форму куба и состоит из
N^3 одинаковых кубических помещений. Между некоторыми помещениями есть двери
или люки. На переход из одного помещения в соседнее (все равно, по
горизонтали или по вертикали) требуется 1 минута. Известны координаты входов
в бункер и координаты помещения, где скрываются террористы. На вход в бункер
также требуется 1 минута. Требуется найти минимальное время, которое
потребуется группе захвата, чтобы добраться от входа в бункер до террористов.
Формат входных данных:
В первой строке содержится целое N - размер бункера, 2<=N<=20. Во второй
строке содержатся координаты x, y, z помещения, в которое должна добраться
группа захвата. В третьей строке записано целое M - количество дверей и люков
между соседними помещениями. В следующих M строках описываются двери и люки,
по одному описанию в строке. Каждое описание задано в формате x1 y1 z1 x2 y2 z2,
где (x1, y1, z1) и (x2, y2, z2) координаты двух соседних (по горизонтали или по вертикали)
помещений, между которыми есть проход. В следующей строке записано целое
число K - количество входов в бункер, 1<=K<=N2. Последние K строк файла
содержат координаты помещений, имеющих выход наружу, в каждой строке записана
одна тройка целых чисел x y z. Числа в строках разделяются одним или
несколькими пробелами. Все координаты - целые числа от 1 до N.
Формат выходных данных:
Минимальное время движения от входа в бункер до помещения, занятого
террористами. Если этого помещения достигнуть невозможно, программа
должна вывести число 0.
Пример входных данных:
3
1 2 1
15
1 2 3 1 2 2
1 2 3 1 1 3
1 1 3 2 1 3
2 1 3 3 1 3
3 1 3 3 2 3
3 2 3 2 2 3
3 3 2 3 3 1
3 3 2 2 3 2
2 3 2 2 2 2
2 2 2 1 2 2
1 1 1 1 2 1
1 1 1 2 1 1
2 1 1 2 2 1
2 2 1 3 2 1
3 2 1 3 3 1
1
2 2 3
Пример выходных данных:
16
|
