Задача C. Площадь
Задачу добавил: alef
Успешно сдано решений: 147
Кеша любит кататься на роликах. Один из его любимых маршрутов пролегает через площадь. Когда-то площадь была покрыта асфальтом, но не так давно асфальт заменили плиткой. Плитка далеко не самое подходящее дорожное покрытие для любителей роликов, поэтому Кеша едет только параллельно сторонам площади. К тому же некоторые плитки расколоты, и на них Кеше уж совсем не хотелось бы наезжать.
Ваша задача — по заданной карте площади найти для Кеши кратчайший маршрут, такой, чтобы, во-первых, Кеша не наезжал ни на какую расколотую плитку, во-вторых, содержащий наименьшее количество поворотов.
Кеша всегда стартует от левого верхнего угла площади и направляется в правый нижний угол.
Гарантируется, что существует хотя бы один маршрут, при движении по которому Кеша не наедет ни на одну расколотую плитку.
В первой строке содержатся целые числа n и m (2 ≤ n, m ≤ 500) — размеры площади в плитках.
Следующие n строк содержат по m символов '.' и 'X', обозначающие, соответственно, целую и расколотую плитку.
В первой строке выведите целое число k — длину маршрута Кеши.
Во второй строке выведите последовательность из k - 1 символа 'L', 'R', 'U', 'D', показывающих, в каком направлении (влево, вправо, вверх или вниз) Кеша должен двигаться.
5 6
.X....
....X.
...X..
X.X...
....X.
12
DRRRURRDDDD
Баллы начисляются за каждый пройденный тест.