Квесты гильдии: распределить пятерых

тема: Перебор с возвратом · уровень: средний

Условие

В настольной игре про гильдию героев есть 5 персонажей (№1…№5) и 5 квестов (№1…№5). Мастер игры дал таблицу: может ли персонаж i ходить в квест j.

Нужно раздать квесты так, чтобы:

каждый персонаж получил ровно один квест;
каждый квест достался ровно одному персонажу;
разрешённость из таблицы соблюдалась.

Если вариантов несколько, выведите лексикографически минимальный список из 5 чисел q1 q2 q3 q4 q5, где qi — квест персонажа i.

Формат ввода

5 строк по 5 символов 0 или 1. Символ в строке i и столбце j равен 1, если персонаж i может идти в квест j, и 0 иначе.

Формат вывода

Одна строка: 5 целых чисел q1 q2 q3 q4 q5 (от 1 до 5) — квесты для персонажей 1…5 в лексикографически минимальном допустимом распределении.

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

Всегда ровно 5 персонажей и 5 квестов.
Ввод состоит только из 0/1.
Гарантируется, что существует хотя бы одно корректное распределение.

Пример

Ввод:

Вывод:

2 1 3 4 5

Разберись руками

Есть 5 персонажей и 5 квестов. В каждой строке написано, какие квесты разрешены конкретному персонажу. Нужно раздать всем по одному квесту без повторов и получить самый маленький по лексикографическому порядку список (сначала важнее q1, потом q2 и т.д.).

Посмотри на 1-ю строку: "11000". Отметь номера квестов (1..5), куда может пойти персонаж 1.
Хотим лексикографически минимально, значит сначала пробуем для персонажа 1 самый маленький вариант: квест 1. Сразу проверь: сможет ли тогда персонаж 2 получить какой-то квест (не занятый и разрешённый)?
Тогда для персонажа 1 берём следующий вариант: квест 2. Теперь какой квест ОБЯЗАН получить персонаж 2 (единственный возможный и не занятый)? Введи номер квеста.
Дальше всё почти фиксировано. Досимулируй раздачу для персонажей 3, 4, 5: на каждом шаге впиши текущее состояние q1..q5 (невыданные помечай _).

Идея: Идём по персонажам слева направо и пробуем давать им самый маленький возможный квест. Если из-за выбора кто-то дальше остаётся без вариантов, откатываем этот выбор и пробуем следующий. Как только дошли до конца без конфликтов — это и будет лексикографически минимальный ответ.

Решить задачу с автопроверкой на Python →

Куда дальше

Школьный этап ВсОШ по информатике — как устроен первый этап и план подготовки за четыре недели
Перечневые олимпиады по информатике — олимпиады перечня Минобрнауки, их уровни и что нужно к диплому
БВИ по олимпиадам: в какие вузы берут — правила приёма вузов, разобранные построчно, со ссылкой на приказ у каждой строки