Задача 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».».
Ответы
Ответ:
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,m,k;
cin>>n>>m>>k;
if(k==m*n-1){
cout<<"IMPOSSIBLE";
return 0;
}
char a[n][m];
for(int i = 0; i<n; i++){
for(int j = 0; j<m; j++){
if(k>0){
a[i][j]='U';
k--;
cout<<'U';
} else if((a[i-1][j]=='U' || i==0) && i==n-1 && j!=m-1){
cout<<'R';
} else if((a[i-1][j]=='U' || i==0) && i==n-1 && j==m-1){
a[i][j] = 'L';
cout<<'L';
} else if(i==n-1 && a[i-1][j]!='U') {
cout<<'U';
} else {
cout<<'D';
}
}
cout<<endl;
}
return 0;
}
Объяснение
код написан на языке с++;
есть 5 случаев которые приведены в картинках ниже + случай когда n*m-1=k выводит Impossible
