Ограничения: время – 1000ms/2000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Корабль Одиссея проплывает через архипелаг, населённый сиренами. Архипелаг состоит из клеток и имеет форму
прямоугольника (`N` строк в высоту и `M` столбцов в ширину). Корабль плывёт из левой верхней клетки в правую нижнюю, перемещаясь между клетками,
соседними по стороне (вверх, вниз, влево или вправо). Одну и ту же клетку можно посещать несколько раз.
В каждой клетке архипелага живёт сирена, непрерывно издающая одну из `7` нот (обозначаемых строчными буквами от `a` до `g`). Ноты,
которые моряки слышат в клетках вдоль пути, образуют песню. Если окажется, что песня содержит в качестве подстроки любой палиндром длины `2` или больше,
то любой моряк, услышавший её, сойдёт с ума и до цели не доберётся.
Найдите минимальную длину (количество перемещений между клетками) пути, по которому корабль Одиссея сможет добраться до цели, и
какой-нибудь из путей минимальной длины. ||.llm|Выполнение вычислений реализовать как функцию с именем raschet, которой передаются входные данные как аргументы.||
Первая строка входных данных содержит `2` положительных целых числа `N` и `M` (`2 <= N * M <= 10^5`) -- размеры архипелага.
Далее следует `N` строк по `M` символов в каждой -- карта архипелага. Для каждой клетки указана буква -- нота, которую издаёт живущая в ней сирена.
В первой строке выведите единственное целое число `K` -- количество перемещений в кратчайшем пути от верхней левой клетки
до правой нижней. Если ни одного пути не существует, выведите 0.
Если хотя бы один кратчайший путь существует, во второй строке выведите его описание: `K` символов без пробелов. Каждое
перемещение обозначается символом ``L``, ``R``, ``U`` или ``D`` (влево, вправо, вверх или вниз соответственно).
```sample Пример ввода 1
3 6
aaadde
bbcbca
cdbbba
```
```sample Пример вывода 1
15
DDRRUURDRRULDDR
```
Путь для первого примера приведён на рисунке. Последовательность нот вдоль него: ``abcdbcadbcdeacba`` (эта строка не содержит в качестве
подстроки ни одного палиндрома длины больше `1`).
Можно показать, что более коротких путей для такого архипелага не существует.
```sample Пример ввода 2
1 3
aba
```
```sample Пример вывода 2
0
```
Начало
Рабочее место участника
Поиск в ширину (BFS)