`Всеукраїнський центр проведення олімпіад в мережі Інтернет

Задача Game3

(предоставлена детективом-любителем)

Ловил я однажды бандита в лабиринте H на W клеток, часть из которых - стенки, а часть - коридоры. Стенами, естественно, окружен весь лабиринт, открытого выхода там не было. И у меня было гуманное оружие, которое стреляло иглами с парализующим на некоторое время ядом. Чтобы поразить бандита, мне нужно было оказаться с ним на одной горизонтали или вертикали так, чтобы между нами не было cтены. И он, и я шагать могли по очереди, и только на одну клетку, имеющую с той, в которой находится шагающий общую сторону. Если я не сумею поразить бандита за К шагов, то сам усну от усталости. Напишите программу, которая поможет мне усыпить бандита.

Ограничения:

1<H,W<=10; 1<K<=1000.

Начальные положения детектива и бандита таковы, что детектив не может сразу же поразить бандита.

Ввод/вывод:

Программа должна прочитать с клавиатуры: с первой строки - число K, со второй строки - два числа H и W, а со следующих H строчек по W чисел - карту лабиринта. Коридор обозначается числом 0, стена - числом 1, бандит - числом 2, детектив - числом 3. Затем начинается погоня. Программа должна по очереди на отдельных строчках выводить шаги детектива либо вводить шаги бандита. Шаги обозначаются буквами L, R, U, D, S, если участник погони ходит на клетку влево, вправо, вверх, вниз

или остается на месте соответственно. Погоня начинается ходом детектива и заканчивается, когда детектив оказывается на одной горизонтали или вертикали с преступником и между ними нет препятствий, или когда детектив сделает K-ый ход (детектив может подстрелить преступника и на K-ом ходу).

Пример:

Ввод> 10

Ввод> 5 7

Ввод> 1 1 1 1 1 1 1

Ввод> 1 0 3 0 0 0 1

Ввод> 1 1 1 1 1 0 1

Ввод> 1 0 0 0 2 0 1

Ввод> 1 1 1 1 1 1 1

Вывод> R

Ввод> L

Вывод> R

Ввод> L

Вывод> R

Ввод> L

Вывод> D

Ввод> S

Вывод> D

В этом примере детектив за пять ходов загнал бандита в тупик и на последнем ходу ловким выстрелом поразил преступника.

© LIKT 1998-2024