Задача M. Побег из Backrooms ≡

Автор:	Борошенко О. Д.		Ограничение времени:	2 сек
Входной файл:	test.sql		Ограничение памяти:	256 Мб
Выходной файл:	test.log

Условие

Вы оказались в Backrooms — бесконечных комнатах, заполненных опасными сущностями. Вам нужно найти кратчайший путь к выходу, используя поиск в ширину (BFS).

База данных содержит информацию о комнатах и связях между ними. В таблице room хранятся:

• id — уникальный идентификатор комнаты
• level — уровень Backrooms (1, 2, 3...)
• x, y — координаты комнаты на уровне
• room_type — тип комнаты ('safe' - безопасная, 'hazard' - опасная)
• is_exit — является ли комната выходом (1 - да, 0 - нет)
• is_entity — есть ли в комнате сущность (1 - да, 0 - нет)
• entity_name — имя сущности (если есть)

В таблице connection хранятся связи между комнатами:

• from_room_id — ID комнаты, из которой идёт переход
• to_room_id — ID комнаты, в которую идёт переход
• direction — направление ('up', 'down', 'left', 'right')
• is_blocked — заблокирован ли проход (1 - да, 0 - нет)

Ваша задача — написать SQL-запрос, который для каждого уровня найдёт комнату, с которой нужно начать путь, чтобы добраться до выхода за наименьшее количество шагов, и выведет:

1. Номер уровня (level)
2. ID стартовой комнаты (start_room_id)
3. Координаты стартовой комнаты (start_x, start_y)
4. Кратчайшее расстояние до выхода (steps) в количестве переходов
5. Количество опасных комнат (hazard_count) на найденном пути

Критерии выбора стартовой комнаты (в порядке приоритета):

1. Минимальное количество шагов до выхода
2. Минимальное количество опасных комнат на пути
3. Минимальный ID комнаты (при равенстве первых двух критериев)

Важно:

• Путь не должен проходить через комнаты с сущностями (is_entity = 1), включая стартовую комнату
• Путь не должен проходить через заблокированные проходы (is_blocked = 1)
• Выходом считается комната с is_exit = 1
• Стартовая комната не должна быть выходом
• Стартовая комната не должна содержать сущность
• В подсчет hazard_count включаются все опасные комнаты на пути, включая стартовую (если она опасна), но исключая выход
• Если на уровне нет пути к выходу, такие уровни не включать в результат

Отсортировать результат по номеру уровня.

Подсказка: В SQLite есть рекурсивные CTE (WITH RECURSIVE), которые позволяют реализовать BFS.

CREATE TABLE Room (
    id          INTEGER not null primary key,
    level       INTEGER not null,
    x           INTEGER not null,
    y           INTEGER not null,
    room_type   VARCHAR(50) not null,
    is_exit     INTEGER not null default 0,
    is_entity   INTEGER not null default 0,
    entity_name VARCHAR(100)
);

CREATE TABLE Connection (
    from_room_id INTEGER not null,
    to_room_id   INTEGER not null,
    direction    VARCHAR(10) not null,
    is_blocked   INTEGER not null default 0,
    primary key (from_room_id, to_room_id),
    foreign key (from_room_id) references Room(id),
    foreign key (to_room_id) references Room(id)
);

Решение следует представить в виде текстового файла, содержащего единственный SQL-запрос.

Формат входного файла

Пример тестовой БД.

Формат выходного файла

Для тестовой базы корректный запрос вернёт следующее:

1|317|2|3|1|0 2|410|2|2|1|0 4|600|0|0|1|0

Ограничения

Предполагается, что для работы с базой данных используется SQLite3.

---