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")