Лабиринт
представляет собой клетчатый прямоугольник MxN, в котором некоторые
клетки пустые, среди этих пустых клеток K клеток имеют под собой бомбоубежище,
а остальные представляют из себя монолитные бетонные блоки.
Военное руководство решило взорвать этот лабиринт "к чертовой матери"1.
Для этого в лабиринте находятся K солдат, которые должны активировать взрывной
механизм. После того, как механизм активирован, солдаты должны укрыться в
бомбоубежищах. К сожалению, в каждом бомбоубежище может укрыться только один
солдат.
Посчитайте минимальное время от момента активации взрывного механизма до
момента взрыва, которое необходимо, чтобы все солдаты укрылись в бомбоубежищах.
Солдат тратит 1 секунду на то, чтобы из клетки, где он находится, перейти в
соседнюю с ней по горизонтали или вертикали и еще 3 секунды на то, чтобы
спуститься из клетки в бомбоубежище, которое под ней находится. Выходить из
лабиринта солдатам запрещено.
1"К чертовой матери" - сверхсекретный военный термин.
input:
Во входном файле
записаны числа M и N (1 ≤ M,N ≤ 100), задающие
размеры лабиринта, а затем N строк по M чисел в каждой, задающие
лабиринт. 0 обозначает пустую клетку, 1 - монолитный бетонный блок, 2 - пустую
клетку с бомбоубежищем под ней. Клеток с цифрой "2" будет ровно K
штук (1 ≤ K ≤ 100). Затем идет K пар чисел, задающих начальные
координаты солдат. Левый верхний угол лабиринта имеет координаты (1,1), левый
нижний- (1,N), правый нижний - (M,N).
output:
В выходной файл
выведите одно число T - минимальное число секунд, через которое можно
взрывать бомбу. Затем для каждой секунды (с первой по T-ую), в отдельной
строке записать передвижения, которые в эту секунду происходят. Действия
задаются номером солдата, и его перемещением, которые записываются через
пробел. Перемещение задается одним из символов N - вверх, S -
вниз, E - направо, W - налево, D - спускается в убежище.
Действия, происходящие в одно и то же время, отделяются друг от друга пробелом.
Если всем солдатам спрятаться не удастся, выведите 0.
|
sample
input #1:
10 5
0 0 1 2 1 0 0 0 0 0
0 0 1 2 1 0 0 0 0 0
0 0 1 1 1 0 0 0 0 0
0 0 2 2 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
4 1
5 4
4 1
6 3 |
sample
output #1:
6 1 D 2 W 4 S 1 D 3 S 2 W 4 W 1 D 2 D 3 D 4 W 4 D 4 D 2 D 3 D 2 D 3 D 4 D
|
|
sample
input #2:
10 5 0 0 1 2 1 0 0 0 0 0 0 0 1 2 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 1 5 4 4 1 4 1
|
sample
output #2:
0
|
