printРабочее место участника

printЗадачи

834. Витрина

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Зал супермаркета имеет форму прямоугольника размером `M`x`N`, в котором расставлены витрины размером 1x1. Стороны витрин параллельны стенам супермаркета, а расстояния от витрин до стен – целые числа.
В супермаркет привезли новую супервитрину размером `K`x1 и выгрузили в одном из углов супермаркета. Требуется передвинуть ее в противоположный угол супермаркета. При этом ее нельзя поворачивать, а можно лишь передвигать параллельно стенам супермаркета. Напишите программу, которая по плану супермаркета поможет определить, какое наименьшее количество витрин нужно убрать, чтобы передвинуть супервитрину.
В первой строке входного файла записаны три натуральных числа `M`, `N` и `K` (`M,\ N\ ≤\ 100`, `K\ ≤\ M`). Начальное и конечное расположение супервитрины такие, как указано на верхнем рисунке. В следующей строке записано целое неотрицательно число `V` – количество витрин (`0\ ≤\ V\ ≤\ N*M`). В следующих `V` строках входного файла записаны различные пары целых неотрицательных чисел, характеризующие положения витрин. Первое число (от 0 до `M-1`) – расстояние от левой стены супермаркета до витрины, второе (от 0 до `N-1`) – расстояние от нижней стены до витрины (см. нижний рисунок). Гарантируется, что там, где изначально поставили супервитрину, других витрин нет.
В первой строке выходного файла выведите минимальное количество витрин, которые необходимо убрать. Во второй строке выведите возможный маршрут передвижения супервитрины в следующем формате. Выводится строка из заглавных латинских букв, обозначающих следующее:
  • U – на 1 вверх,
  • D – на 1 вниз,
  • L – на 1 влево,
  • R – на 1 вправо.
Количество символов в строке не должно превышать `N`x`M`.
Если возможных маршрутов несколько, то выведите любой из них.

Пример ввода 1

10 10 5
0

Пример вывода 1

0
RUURUURUURUURU

Пример ввода 2

9 3 2
4
2 0
5 1
5 2
8 2

Пример вывода 2

1
URRRDRRRRUU
Решения, верно определяющие маршрут передвижения супервитрины в случае, когда убирать ни одной витрины не нужно, будут набирать 50 баллов.
Московская городская олимпиада школьников по информатике, 2008
loading