aiym19

16.06.2022 12:58

Информатика

Есть ответ 👍

Квест новый квест, в котором участники должны выбраться с территории проведения, представляет собой прямоугольник из n × m комнат. каждая комната имеет четыре двери, ведущие в соседние комнаты, из комнат на краю прямоугольника двери ведут наружу, через эти двери можно покинуть территорию проведения квеста. в начале квеста в каждой комнате находится по человеку, а все двери заперты. после начала квеста организаторы дистанционно открывают в каждой комнате запирающий механизм одной из четырёх дверей. теперь человек, находящийся в этой комнате, может открыть эту дверь и перейти в соседнюю комнату, через другие три двери выйти из этой комнаты нельзя. при этом может оказаться так, что дверь, соединяющая две комнаты, будет отпираться только с одной стороны, тогда пройти через эту дверь можно только с той стороны, с которой она будет открываться, проходить через дверь в обратном направлении нельзя, если в соседней комнате будет отперта не эта дверь, а какая-то другая. если комната находится на краю территории и из этой комнаты открыта дверь наружу, то, пройдя через эту дверь, участник навсегда покидает территорию квеста. после начала квеста и отпирания дверей участники начинают перемещаться между комнатами. каждый участник перемещается в соседнюю открытую комнату и продолжает перемещаться до тех пор, пока не покинет территорию квеста. однако возможна ситуация, когда некоторые участники будут бесконечно перемещаться между комнатами и никогда не выйдут наружу. разработчки квеста попросили вас составить такой план отпирания дверей, при котором ровно k человек смогут выбраться наружу с территории квеста. желательно на c++