Ctrl K

Рассадка на экзамене без списывания

Сложная
Аудитория задана таблицей hall из m рядов по n мест. '.' — исправное место, '#' — сломанное, на него садиться нельзя. Ряд 0 — ближний к доске. Студент видит работы тех, кто сидит рядом с ним слева и справа в том же ряду, а также тех, кто сидит в ряду перед ним по диагонали — слева-спереди и справа-спереди. Работу студента прямо перед собой или прямо за собой он не видит. Верните наибольшее число студентов, которых можно рассадить так, чтобы никто ни у кого не мог списать.
Пример 1
hall=[['.', '.', '.'], ['.', '#', '.']] → 4

В первом ряду сажаем на места 0 и 2, во втором — тоже на 0 и 2. Прямо друг за другом сидеть можно, а по диагонали и рядом никто не оказался: 4 студента.

Пример 2
hall=[['.', '.'], ['.', '.']] → 2

В каждом ряду помещается только один студент (соседи сбоку подглядывают), и сажаем их в одном столбце: 2.

Ограничения
  • 1 ≤ m ≤ 8
  • 1 ≤ n ≤ 8
  • каждая клетка hall[i][j] — '.' или '#'
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиКоммутация двух панелей СложнаяПо одному с каждой полки СложнаяКак рассчитаться за меньше переводов СложнаяДве группы с одинаковым средним СложнаяСклейка фрагментов Сложная
загружаем Python…
Вход
hall=[['.', '.', '.'], ['.', '#', '.']]
Ожидается
4

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 67 тестов на сервере, включая скрытые.