Роботы на складе: сколько расстановок
Условие
На складе школьной команды по робототехнике стоит квадратная сетка из клеток. В некоторые клетки нельзя ставить роботов (там ящики). Вы хотите поставить ровно K одинаковых роботов так, чтобы они не мешали друг другу.
Робот «мешает» другому, если они стоят в одной строке или в одном столбце (как ладьи в шахматах). Ящики не экранируют: важно только совпадение строки или столбца.
Посчитайте, сколькими способами можно поставить ровно K роботов.
Формат ввода
В первой строке два целых числа N и K (1 ≤ N ≤ 8, 0 ≤ K ≤ N). Далее идут N строк по N символов каждая.
.— клетка свободна#— клетка занята ящиком, ставить робота нельзя
Формат вывода
Выведите одно целое число — количество расстановок ровно из K роботов.
Ограничения
1 ≤ N ≤ 8, 0 ≤ K ≤ N. Клетки с # запрещены. В одной строке и в одном столбце может стоять не более одного робота.
Пример
Ввод:
4 2
....
....
....
....Вывод:
72Разберись руками
Есть поле 4×4 без ящиков (везде точки). Нужно поставить ровно 2 одинаковых робота так, чтобы они не оказались в одной строке или в одном столбце.
- Как удобнее считать, чтобы не запутаться и не пересчитать одно и то же несколько раз?
- Сколькими способами можно выбрать 2 разные строки из 4 (порядок строк не важен)?
- Теперь так же: сколькими способами выбрать 2 разные колонки из 4?
- Допустим, строки уже выбраны (например, 1-я и 3-я) и колонки тоже выбраны (например, 2-я и 4-я). Сколько разных корректных расстановок 2 роботов можно сделать на пересечениях этих строк и колонок?
Идея: Сначала решаем, какие строки будут заняты роботами, и какие столбцы будут заняты. Потом для каждого такого выбора считаем, сколькими способами можно раздать выбранные столбцы выбранным строкам так, чтобы в каждой строке и каждом столбце оказался не больше один робот.
Решить задачу с автопроверкой на Python →
Куда дальше
- Школьный этап ВсОШ по информатике — как устроен первый этап и план подготовки за четыре недели
- БВИ по олимпиадам: в какие вузы берут — правила приёма вузов, разобранные построчно, со ссылкой на приказ у каждой строки
- Перечневые олимпиады: что это и что дают — весь перечень Минобрнауки: уровни, срок диплома, разрезы по предметам и классам