Выбор ответа Senior Перебор с возвратом обновлено
Ферзи: проверка за O(1)
Вопрос
В задаче о n ферзях как проверить за O(1), что клетка (r, c) не бьётся?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Три Set: столбцы, диагонали r - c и антидиагонали r + c. Ставим по одному ферзю в строку, значит строки не конфликтуют.
Варианты ответа
- Проверять всю доску на каждом шаге: это O(1), так как n фиксировано
- Три Set: столбцы, диагонали
r - cи антидиагоналиr + cправильный ответ - Три множества: столбцы, диагонали
r - cи антидиагоналиr + c - Сортировать позиции ферзей и проверять бинпоиском соседние клетки
Разбор
Ставим по одному ферзю в строку, значит строки не конфликтуют. На одной диагонали постоянна разность r - c, на антидиагонали сумма r + c. Три Set дают проверку O(1).
- Проверка доски O(n²) на каждый шаг.
- Строки и так уникальны, проблема в столбцах и диагоналях.
- Сортировка не помогает.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.