Задача A. Город перекрёстков Вы разрабатываете навигатор для одного города. Этот город разбит улицами на квадратные кварталы, причём движение по любому из отрезков улицы в пределах каждого квартала строго одностороннее. С каждого перекрёстка можно выехать только в разрешённых знаками направлениях. Требуется по прилагаемой карте города с указанными на ней разрешёнными направлениями перемещения проложить самый короткий маршрут из точки AA в точку BB.

Формат входных данных

На вход подаётся карта перекрёстков города. В первой строке содержатся два числа NN — число кварталов с севера на юг и MM — число кварталов с запада на восток (1 ≤ n ≤ 50). Точка AA самая северо-западная, точка BB самая юго-восточная. Далее в 2*N+12∗N+1 строках содержится описание разрешённых направлений движения. Улицы города запад-восток описаны в нечётных строках. В каждой такой строке содержится по MM символов без пробела, указывающих разрешённое движение на соответствующем участке. В чётных строках содержится описание улиц север-юг. В этих строках содержится по M+1M+1 символов, указывающих возможное движение по отрезкам улиц север-юг. Движение на север, юг, запад, восток обозначается буквами n, s, w, e соответственно.

Формат выходных данных

В первую строку вывести число отрезков улиц в самом коротком маршруте из точки AA в точку BB. Во вторую строку нужно выдать описание этого маршрута в виде последовательности символов n, s, w, e без пробелов. Если кратчайших маршрутов несколько, выдать самый первый среди них по алфавитному порядку. Гарантируется, что из точки AA можно попасть в точку BB.

Пояснение к первому примеру

Sample Input 1:

4 5
w
sn
wewww
snsnns
weeew
snnsns
wwwew
ns
w
Sample Output 1:

29

Sample Input 2:

2 2
ee
sss
ee
sss
ee
Sample Output 2:

4
eess


Задача A. Город перекрёстков Вы разрабатываете навигатор для одного города. Этот город разбит улицам
Задача A. Город перекрёстков Вы разрабатываете навигатор для одного города. Этот город разбит улицам

Юличка111333 Юличка111333    2   16.10.2020 07:15    16

Другие вопросы по теме Информатика