|
Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
- Винни, Винни! Смотри: в твоём половичке моль проела дырки!
Давай этот выбросим, а другой положим - помнишь, тебе Кролик
дарил два одинаковых квадратных зелёных клетчатых половичка? Интересно, можно ли поверх одного половичка Винни-Пуха положить другой, чтобы их дырявые клетки не совпадали? Половички можно как угодно поворачивать и переворачивать (они двухсторонние), но их границы должны совпадать. Разработайте программу, определяющую, сколько совмещённых дырок останется при оптимальном (скрывающем максимум дырок) положении половичков? Входные данные: в первой строке натуральное число N, не превышающее 20 - сторона коврика в клетках. Далее следуют 2*N строк, описывающих клетки ковриков. Каждая строка состоит из N цифр 0 или 1 (0 - клетка с дыркой, 1 - целая). Выходные данные: Целое число - минимальное количество клеток с дырками, которые остались совпадающими в двух ковриках при оптимальном их расположении. Для отправки решений необходимо выполнить вход. |