Ограничения: время – 1500ms/3000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Гааль Дорник экспериментирует с передачей информации с помощью зеркал.
Площадка размером `N xx M` разбита на клетки единичного размера.
Нужно отправить луч света из одной клетки в другую. Луч проходит параллельно осям координат.
Специальные зеркала установлены в некоторых клетках площадки и по всему периметру площадки. Зеркало изменяет направление луча на 90 градусов,
при этом часть света направляется в одну сторону, а часть в противоположную.
Так как при каждом отражении энергия луча уменьшается, то желательно, чтобы отражений было как можно меньше.
Необходимо определить начальное направление, которое позволит лучу добраться до целевой клетки с минимальным количеством отражений.
Первая строка ввода содержит семь целых чисел -- размеры площадки `N` и `M` (`2<=N, M<=10^5`), координаты
начальной клетки `R_1, C_1` и целевой клетки `R_2, C_2` (`1 <= R_1, R_2 <= N`, `1 <= C_1, C_2 <= M`, `(R_1,C_1)!=(R_2,C_2)`),
количество зеркал на площадке `K` (`0<=K<=10^5`).
Далее следует `K` строк, каждая строка содержит два целых числа -- координаты `i`-го зеркала `r_i,c_i` (`1 <= r_i<=N`, `1<=c_i<=M`).
Координаты зеркал не совпадают между собой и не совпадают с координатами начальной и конечной точки.
Кроме того, зеркала установлены в клетках с координатами `(0,j)`, `(N+1,j)`,`(i,0)`, `(i,M+1)`, где `i in 0...N+1`, `j in 0...M+1`.
Вывести минимальное количество отражений и начальное направление (N, E, S, W) или -1, если луч не может достичь конечной клетки.
Если есть несколько вариантов направления для начальной клетки, обеспечивающих минимальное количество отражений, то можно вывести любой из них.
```sample Пример ввода
5 7 4 6 1 3 3
2 3
2 5
5 5
```
```sample Пример вывода
4 N
```
*Пояснение к примеру:*
При выборе других направлений получится не менее 5 отражений.
Начало
Рабочее место участника
Поиск в ширину (BFS)