Задача 5. Квест
Новый квест, в котором участники должны выбраться с территории проведения,
представляет собой прямоугольник из N × M комнат. Каждая комната имеет четыре двери, ведущие
в соседние комнаты, из комнат на краю прямоугольника двери ведут наружу, через эти двери можно
покинуть территорию проведения квеста.
В начале квеста в каждой комнате находится по человеку, а все двери заперты. После начала
квеста организаторы дистанционно открывают в каждой комнате запирающий механизм одной
из четырёх дверей. Теперь человек, находящийся в этой комнате, может открыть эту дверь и перейти
в соседнюю комнату, через другие три двери выйти из этой комнаты нельзя. При этом может
оказаться так, что дверь, соединяющая две комнаты, будет отпираться только с одной стороны, тогда
пройти через эту дверь можно только с той стороны, с которой она будет открываться, проходить
через дверь в обратном направлении нельзя, если в соседней комнате будет отперта не эта дверь,
а какая-то другая. Если комната находится на краю территории и из этой комнаты открыта дверь
наружу, то, пройдя через эту дверь, участник навсегда покидает территорию квеста.
После начала квеста и отпирания дверей участники начинают перемещаться между
комнатами. Каждый участник перемещается в соседнюю открытую комнату и продолжает
перемещаться до тех пор, пока не покинет территорию квеста. Однако возможна ситуация, когда
некоторые участники будут бесконечно перемещаться между комнатами и никогда не выйдут наружу.
Разработчки квеста попросили Вас составить такой план отпирания дверей, при котором
ровно K человек смогут выбраться наружу с территории квеста.
Программа получает на вход три числа N, M, K, 1 ≤ N ≤ 100, 1 ≤ M ≤ 100, 0 ≤ K ≤ NM. N и M –
количество строк и столбцов в прямоугольном плане квеста, K – количество человек, которые должны
выйти из квеста.
Программа должна вывести план территории квеста в виде N строк, каждая из которых
должна содержать M символов. Символ соответствует тому, какая дверь будет открыта в данной
комнате и может быть одной из следующих заглавных английских букв: U (дверь в верхнюю
по данному плану комнату), D (дверь в нижнюю комнату), L (дверь в левую комнату), R (дверь
в правую комнату). Необходимо вывести один любой подходящий план решения задачи. Если
ни одного подходящего плана не существует, программа должна вывести одну строчку
«IMPOSSIBLE».».
Ответы
Очевидно, решения нет, если нужно выпустить ровно K = NM - 1 человека: он должен перейти в какую-то комнату, но из всех комнат, кроме его, есть путь наружу.
При всех остальных K можно, например, поступить так:
- отсчитать сверху и слева направо K комнат, в них открыть дверь вверх
- в оставшихся комнатах, не находящихся в нижнем ряду, открыть путь вниз
- в оставшихся комнатах нижнего ряда, кроме правого нижнего угла, открыть дверь вправо
- в правом нижнем углу, если там ещё не открыта дверь, открыть дверь влево
В итоге K человек уйдут с территории через верх, а остальные будут бесконечно ходить между двумя комнатами в правом нижнем углу.
Код (python 3):
N, M, K = map(int, input().split())
if K == N * M - 1:
print("IMPOSSIBLE")
elif K == N * M:
for _ in range(N):
print("U" * M)
else:
for _ in range(K // M):
print("U" * M)
if K // M < N - 1:
print("U" * (K % M) + "D" * (M - K % M))
for __ in range(N - 1 - K // M):
print("D" * M)
print("R" * (M - 1) + "L")
else:
print("U" * (K % M) + "R" * (M - K % M - 1) + "L")