#608

Витрина

Темы: [Алгоритм Дейкстры] [Обход в ширину]

Источники: [ Личные олимпиады, Московская олимпиада школьников, 10-11 классы, 2008, 1 день, Задача B ]

Зал супермаркета имеет форму прямоугольника размером \(M\) x \(N\), в котором расставлены витрины размером 1 x 1. Стороны витрин параллельны стенам супермаркета, а расстояния от витрин до стен – целые числа.

В супермаркет привезли новую супервитрину размером \(K\) x 1 и выгрузили в одном из углов супермаркета. Требуется передвинуть ее в противоположный угол супермаркета. При этом ее нельзя поворачивать, а можно лишь передвигать параллельно стенам супермаркета. Напишите программу, которая по плану супермаркета поможет определить, какое наименьшее количество витрин нужно убрать, чтобы передвинуть супервитрину.

Входные данные

В первой строке вводятся три натуральных числа \(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\).

Если возможных маршрутов несколько, то выведите любой из них.

Примеры

Входные данные

10 10 5
0

Выходные данные

0
RUURUURUURUURU

Входные данные

Выходные данные

1
URRRDRRRRUU

#645

Lines

Темы: [Обход в ширину]

В таблице из \(N\) строк и \(N\) столбцов некоторые клетки заняты шариками, другие свободны. Выбран шарик, который нужно переместить, и место, куда его нужно переместить. Выбранный шарик за один шаг перемещается в соседнюю по горизонтали или вертикали свободную клетку. Требуется выяснить, возможно ли переместить шарик из начальной клетки в заданную, и, если возможно, то найти путь из наименьшего количества шагов.

Входные данные

В первой строке находится число \(N\), в следующих \(N\) строках - по \(N\) символов. Символом точки обозначена свободная клетка, латинской заглавной \(O\) - шарик, \(@\) - исходное положение шарика, который должен двигаться, латинской заглавной \(X\) - конечное положение шарика. 2 <= \(N\) <= 40.

Выходные данные

В первой строке выводится \(Y\), если движение возможно, или \(N\), если нет. Если движение возможно, далее следует \(N\) строк по \(N\) символов - как и на вводе, но буква \(X\), а также все точки по пути заменяются плюсами.

Примеры

Входные данные

2
@.
.X

Выходные данные

Y
@+
.+

Входные данные

2
@O
OX

Выходные данные

#646

Покраска лабиринта

Темы: [Обход в ширину]

Лабиринт представляет собой квадрат, состоящий из NxN сегментов. Каждый из сегментов может быть либо пустым, либо заполненным монолитной каменной стеной. Гарантируется, что левый верхний и правый нижний сегменты пусты. Лабиринт обнесён сверху, снизу, слева и справа стенами, оставляющими свободными только левый верхний и правый нижний углы. Директор лабиринта решил покрасить стены лабиринта, видимые изнутри (см. рисунок). Помогите ему рассчитать количество краски, необходимой для этого.

Входные данные

В первой строке находится число \(N\), затем идут \(N\) строк по \(N\) символов: точка обозначает пустой сегмент, решётка - сегмент со стеной. 3 <= \(N\) <= 33, размер сегмента 3 x 3 м, высота стен 3 м.

Выходные данные

Вывести одно число - площадь видимой части внутренних стен лабиринта в квадратных метрах.

Примеры

Входные данные

4
....
....
....
....

Выходные данные

Входные данные

4
....
.##.
.##.
....

Выходные данные

#651

Lines(2)

Темы: [Обход в ширину]

В таблице из \(N\) строк и \(N\) столбцов некоторые клетки заняты шариками, другие свободны. Выбран шарик, который нужно переместить, и место, куда его нужно переместить. Выбранный шарик за один шаг перемещается в соседнюю по горизонтали или вертикали свободную клетку. Требуется выяснить, возможно ли переместить шарик из начальной клетки в заданную, и если возможно, то найти путь из наименьшего количества шагов.

Входные данные

В первой строке находится число \(N\), в следующих \(N\) строках - по \(N\) символов. Символом точки обозначена свободная клетка, латинской заглавной \(O\) - шарик, \(@\) - исходное положение шарика, который должен двигаться, латинской заглавной \(X\) - конечное положение шарика. 2 <= \(N\) <= 250.

Выходные данные

В первой строке выводится \(Y\), если движение возможно, или \(N\), если нет. Если движение возможно, далее следует \(N\) строк по \(N\) символов - как и на вводе, но \(X\), а также все точки по пути заменяются плюсами +.

Примеры

Входные данные

2
@.
.X

Выходные данные

Y
@.
++

Входные данные

2
@O
OX

Выходные данные

#657

Путь коня

Темы: [Обход в ширину]

Дана шахматная доска, состоящая из \(N\)x\(N\) клеток, несколько из них вырезано. Провести ходом коня через невырезанные клетки путь минимальной длины из одной заданной клетки в другую.

Входные данные

В первой строке задано число \(N\). В следующих \(N\) строках содержится по \(N\) символов. Символом # обозначена вырезанная клетка, точкой - невырезанная клетка, \(@\) - заданные клетки (таких символов два). 2 <= \(N\) <= 50.

Выходные данные

Если путь построить невозможно, вывести "Impossible", в противном случае вывести такую же карту, как и на входе, но пометить все промежуточные положения коня символом \(@\).

Примеры

Входные данные

2
@.
.@

Выходные данные

Impossible

Входные данные

3
@..
...
..@

Выходные данные

@@.
..@
@.@