Codegolf - Сколько Домино Вы Можете Разместить Здесь?

Гораздо сложнее, чем Можно ли сделать этот узор из домино?

Испытание

Дана сетка шириной \$w\$ и высотой \$h\$, заполненная единицами и нулями. Вы можете разместить домино где-нибудь в сетке, только если обе ячейки равны 1. Вы не можете перекрывать домино. Какое максимальное количество домино можно разместить в данной сетке?

Временная сложность в худшем случае должна составлять \$\mathcal{O}(w^2h^2)\$ или ниже. Пожалуйста, объясните, насколько ваш ответ соответствует этому требованию временной сложности. Если вы используете встроенный модуль для решения проблемы, вы должны предоставить доказательства того, что встроенный модуль соответствует ограниченной временной сложности. (Обратите внимание, что «быть полиномиальным по времени» недостаточно.)

Для достижения границы можно использовать по крайней мере два хорошо известных алгоритма: Форда-Фалкерсона и Хопкрофта-Карпа. Существуют также более специализированные алгоритмы с еще лучшим временем выполнения.

Вы можете использовать любые два согласованных значения вместо 1 и 0 во входных данных. Вы можете предположить, что \$w\$ и \$h\$ положительны, а входная сетка имеет прямоугольную форму.

Применяются стандартные правила. Выигрывает самый короткий код в байтах.

Тестовые случаи

В тестовых примерах используются

 O..
OO.
OOO  => 2

..OOOO..
.OOOOOO.
OOO..OOO
OO....OO  => 9

OOOOOOOOOOOOOOOO
O.OOO.OOO.OOO.OO
O..OOO.OOO.OOO.O
OO..OOO.OOO.OOOO
OOO..OOO.OOO.OOO
OOOO..OOO.OOO.OO
O.OOO..OOO.OOO.O
OO.OOO..OOO.OOOO
OOO.OOO..OOO.OOO
OOOO.OOO..OOO.OO
O.OOO.OOO..OOO.O
OO.OOO.OOO..OOOO
OOO.OOO.OOO..OOO
OOOO.OOO.OOO..OO
O.OOO.OOO.OOO..O
OO.OOO.OOO.OOO.O
OOOOOOOOOOOOOOOO  => 80

....OOO..O.OOOOO..OOO.OOO
OO.OOOOOOOO..OOO.O.OO.OOO
OOO.OO.O.O.OOOOO...OO.OO.
.O..OO.OO.OO.OO.O..OOOOOO
O.O.O..OOO..OOO.OOO.O.OOO
O.OOOOOOOOOOOOOO.OO..OOO.
OOOOOO.O.O.OOOOOOOOOOOOOO
O.O.O.OO.OO.O..OO..OOOOOO
O.OOOO.O.OOO.OOOOO.OOOOOO
..OOO..OO...OOOOOOOOOOOOO
.O..OO.OOOO.OO.O..OOOOOOO
O.OOOOOO..OO...OOO.OOOOOO
.OO....OO.OOOOO.OO.OOOOOO
OOOO.OOO.O..OOO.OOOOO...O
...OOOOOO.OOOOOOO.OOOOO.O
O..O.OOOOOOOOOOOOOOOOOOO.
OOOO.O.OOOOOOO..O..OO.O.O
..OOOOOOOOO.OOOOO.OOOO.O.
O.OOOOOOO...OO..O.OOOO.O.
OOO.O.O..OOOOO.OOO.OOO..O
.OOO.OOO.OO.OOO.O.OOOOO..
O.OO..OO..O.....OOOOOOOO.
..OO.O.O.OO.OOO.O.OOOO.O.
OOOOO.OO..OO...O...O.O.OO
O..OOOOOO.O..OOOOO.OOOOO.  => 197

O.O..O.OOOO.OOO..OO.OOOOOOOO.OO...OO.O.O.OOOOOOO.O
OOOO...OOOO..O..OOO.....O..OO.....OOO..OO..OOO.OOO
.OOO..OOOOOOO....O.OOOOO..OO.O..OO.OOO.OO.O.O.OOOO
OOOOO..O...OOOOOOO.O.O....O..O.OOOOOOOO.O..OOOOO.O
OOOOOOO.O.OOOO.OOO.O.O.OO..OOOOOOOOOOOOO.OOOOOOOO.
OO.OO.OOOOO.OO..O.OO.OOO...O.OO.OOOO.OO.OO.....OOO
OOO.OOO.OO.OO...O.OOOOO..O.OOOOOOO.O..O..OO.OOOO..
OOO.O.OOO.OOOOOO.OOOO.OO.OOO..OOO..O.OOO.OO.OOOO..
OO..OOOO.OOOOO.OO..O.OOOOOOOOOOOO.O..O.O.OOO.O.OOO
.OOOO.O.O.O.OOOO.OO.O..OOO..O.O.OOO..OOOOOOOOO..O.
O..O.OOOO.OOOOOOOOO..O..O.O.OOOOOOO...O.OO...O....
OOO...O..OOOO.O.O..OO.O..O.OO..O.OOOOOOOOO..OOOOO.
OOO.OOOO.OO.OO.O..O..OOO..OOOOO.OOO..OOO..OO.OOOOO
O....O.OOOOOO.OOO..OOOOOOOOOOO.O.OOOOOOO.OOO.OOO..
..OOOO..OOOOO..O..O.OOOOOOOOO.OOOOO..OOOOO.OO..O.O
O.OOOO..OO..OOO.OO...OO.OO.OO.OO..O.OO.O.OOOOOO.OO
.OO.O....O..OOOOOOOO.O......O.OO.OO..OOOOO.OOOO.O.
OOOOO.O.OOOOOOO......OOO.O.O.OOOO.OOO.OO.OOOOO.O.O
..O.OO..O.O...OOO.OOOO..OO.OOOO.OOOO.OOO.OOOOOOO.O
OO.OOOOOO...OOO.OOOOOOOOOOOOOOOOOOOO.O...O.O..OO.O
O...O.O.O.OOOO.O.O.O.OO.O...OO..O.O.OOO.O..O.O.O..
OO.O.O.O..OO.O....OOOOO..O.O..OOOO.OOO.OOOO.OOOO..
OOOOOO.OOO.O..OOO..OOOO...OOO.OO.OOOOO.OOO.OO.OOO.
.O..O.O..OOO..O.OO.O.OOOO.O..O..OOOOOO.O..O..O...O
.OOOO.O..O.O..O.OOO.OOO.OO.OOO.O.O.OO.OOO.O..OOO.O
OO.OO...O.OOOOOOOO.OOOO..O.OOOOOO.OOO.OO..OOO.OOOO
OO.O.O..OO..O...O.O.O.OOOO..OO.OOOO.OOO.OO.O..OOO.
OOO....OO.OO..OO.O.OOOO..O.O..OO..O.O.OOOO..O.O..O
..O.OOO.OOOO...OO.OOO..O.O.OO.OO...OOOO.OO.OOO.OOO
O.OOOOOO.O.OO.OOOOOO..OOO.O.OOO.OO..O.O.OOOOOO.O.O
O.OO....O..OOOOO..OOO.O.OOOOOOOOO..O.O..OOOOOO.OOO
.OOOO..OOOO..OOOOO.OOOOO.OOOOOOOOOO..O..OO.OO..O.O
OO.OOOOOO..O.OOOOO..O....OO.OOO.OOO.O.O.OO..OO....
OO.OOO.OOOOOOOOO.O.OO..O.OOOO.OOO.OO.OOOOO...O.O.O
OOOO..OO.O.O.OO.OOOO..O....OOOOOOO.O..O.O.OOO.O.O.
OOO.O.OOO.O.OO..OOOO...OOOOOO.O....OOOOOO.....O..O
OOOO.OOOO.O..OOO...O...OOO.OO.OOOOO..OOOOOOOOOO.O.
..OOOOO..OOO.O..O..OOOO.O.O.OOOOOOOO...O..OO.O..OO
OOOOOO.OOO.O..O.O.OOO...O.O.O..O.O..O.O..OO.OOOOOO
O.OOOOOOOO.O...O..O.O.OOOOOO.O.OO.OOOOOOOOOOOO..OO
O.O.OOOO...OOO.OO.OOOO.OO.O...OO..OOOOOOO.OOO.O.O.
.OO.O..OO.O.OOO.OOO.OO.OOO..OOOOO...O.O..OO...O...
..OOO..O.OOO.OOOO...OOO..OO.OO..O.OO.OOOOOO.O.O.O.
.OOOOO.O..OO.O.OO...O.OOOOOOOOO.OOOOOOO.O.OO.OOOOO
OOO..OO.OOO.OO.OO....OO.O.O.OOOO..O..OO.O..OOOOOO.
..O.OOO...O.OOO.OOOOOOOOOOO...OO.O.OOO.O..OOOOO.OO
..O..OOOO..O...OOOO.OO...O..OO.OO.OOOOO..O.O.OO...
.OOOOO.OOOO.O..OOO.OOOOOOOO....OO.OO.O....O.O..O.O
O.OOOO.O.O.O.O.OOOOOOOO.OOO.OOO.O....OOOOOOO..OOOO
OOOOO.OOOOOOO..OOO.OO.OOOOO.OOOOOO.O.O.O.OOOOO.O.O  => 721

..O.O.OOOO..O.OOOOOO.O.OOOO.O.OO.O.O..OOOOOOOOO.OO.O.OO..O.OOOOOO.O..O
O.OOOOO.OOOOOOO.O.O.OOOOOO..OO.O.OO.....OO.OOOOOOOO.OOOOOOOOO.O..OOO..
OOOOO.OOO.OOO.OO.OOOO..OO.O.OO.OOO.OOOO..OOOOOOOOOO...OO.O..OOOOO.OO.O
.O...OOO...OOO.OO..OO.OOOOOOOOO.OOOOOOOOOOO.O..OOOOOOOOOOOOOOOOO.OO.OO
OO.OO.O.OOOOOOOO.OOO.OO.OOOO.O.OOO.OOO.OOOOO.OOO..OOOOO....O.O.OOO..O.
OO..O.OOOOOO..OO..O..OOO..OO.OO.OOO...OO..O.OOO.O....O..O.OO..OOO.OO.O
OO..OOO..OOOOO.OOOO.O..OO.O.OOO..OOO..O.OOO...OO.OOO..OOOO.OOO.OO.OOO.
OOOOO.OOOOOOOO.O...OOO..OOOO.OOO.O.O.OOO..OOOOO..O.OO.OOOOO......O.OOO
OOOOOO.OOOOO.O.O.OOOOOO.OOOOOO.OOOO.OOOOO.O...OOO.OO..OOOOOOOOOOOOOO.O
OOOO.OOOO...OOO..OOOO.OOOOOOOOOOO.O..OOOOOOOO.OOOOOOO.OOOOOOOOOOOOO.OO
OOOO.OOOOO.OOO.OOO..OOOO..OOO..O..OO.OOOOO.OOOOOOO..OO.OOO...OOO.OOOOO
.OO..O.O.O.O.OOOOOOO.O.OOOOOOOO....O.OOOOO.OOOO.O..OOOOOO..OO.O.O.O.OO
OO..OO.OOOOOO.OOOOOO..OOOOOOOO..OOOOOOOOO.O.OOOO....OOOOO.OOO..O.O...O
O.O.OOOO.O..OOOO.OOOOOO..OOO...OO.O.OOOO.OOOOOO.OO.O..OOO.OOOOO...OOOO
O..OOO.O.OO...O..O..O.OOOO.OOOOOOOO...OOOO...OOO..OOOOOO..OOOOO..OOOOO
OOOO.OOOOO.OOOOO.OOOOO.O..O.OO..O.O.O..O..OOO...O.O.OO.O.O..OOOO.OO..O
OO..OOO.OO...OO..OO.O.OOOOO.O..OOOOOOO..O..OOO.OOO.O..OOO..OOOOO...O.O
.OOOOOOOOO.OOOOO...OOOO..OOOOOOO.OO..OOOOOOOO..OOOO..OOOOOOO...O.OO.OO
.OOOOO.O..O.O.O.O.O...OO..OO.OOO.OOO.OO.OOO...O.O..OOOO.OOOOOOOOOOO.OO
O.OOO.O...OOOO..OOOOOOOO.OOO.OOO.O.OOOO.OOOOOO.O.OO.OO...O.OO.OO..O..O
.OO.O..OOOOO..OOOOOOOO.O.OO.OOO.OO.O...O..OOO.O.OOOO...OO..OOOOOOOOO.O
..OO.OOOO.OO.OO..OO.OOOO..OOOO.OOOOO.OOO.O.O.OO..OO.O.O.OOO.OOOO..OO.O
OOO..O.OOO.O.OOOOOOOOO.OOO.OOO.OOO.OOO.OOO..OO.O.OOOO.OO.OOOOOOOOOO.OO
O...OOOOOOO..O.OO.OO...OOO.O...OO.OOO.OOO..OO..OO..OO.OO..OO..OOOOOOOO
..OOO.O..OO...OOOOO...OOO.OO...OOOO.OOO.OO...O...O.OOOO..OOOOOOOO.OOOO
O..OO..OO.OOO.OOOOOOOO.OOOOOOOOOOOOO..OOOO.O.O.OO.....O..OOO..OO.OOOO.
..OO.OOO.OO.O.O.OO.OOOOOOO.O...OOOOOO.OOO.OOO.O.OO.OOO.OOO.OOO..OOOOOO
OO.O..OO.....OOOOO..OO.OOOO.OOOOOO.O.O.O.O..OOO.OOO.O....OOO.OO..OOOOO
O.OO.O.O.OO.OOOO..OOOO..OO.O.OOOO.OOOO.O..O.OOOO.OO.O....OO..OO.O.OOOO
O..OOO.O...O.OO.OOOOO.....OOOOOOOOO..O.OOO.O.O.OOOOO..O.OOOO....OO..OO
.OOOOO...OOOO..O.OOO.OO.OO.OOOO.OOO.OOOOO.OOO...OOOOO.OOOOOOOO.OOOO..O
O...OOOOO..OOO.......O.OO...O.OOO...OOOOO..OOO..OOOO.OO.OO.O...OOO..OO
O.OOO..OO..OO..OOOOOOOOOOOO.OO.OO.O.OOOO...OO.O.OO..OOO..O...OOO..OOO.
..O.OOOO.O...OOOOO.OOOO.OOOOOO..OOO..OOOO.OO...O.OOO..OO.O..OO.O.OOOOO
..OOO..OOOOO.OOOOOO.OO.O..OO.O..OO.OO.OOOO.O.OOO.OO.OOOOO.O.OO.OOO.OOO
OOO.O.O.OOO.OO.OOOOO.OOO.OOO.O..OO.OO..OOOOOO.OOOOO.OO.OOOOOO....O.OOO
O..O.O.O.OOOO.O.O..O.OOOOO.O.OOOO.OO.OOO..O.OOOO.O.O..OOO.OO..OO..OOOO
OOOO.OOOOO...O..OO...OO.OO.OOO...OOOOOOOO...OO..O...OOOO..O.O...OO.OOO
OOOOOOOOOO.O.O.OO.OOOOOO.OO.OO.OO.O.O.O.O.OOO..OO.OOO.OOO.O..O.OOO..OO
.O.OOO.O.OOOOOOOO.O.O..OOOOOOOOOO.OO..OOOOOO.O.OOO..OOO.OOO.OOO..OOOOO
.O.O.O.OOOO.OOOO.OOOOO.OOOO..OO..OO.O.O..OOO.O..OO.OOOOOOO.....O.OOO.O
OO..O.O..OOOO.OO.OOO.OOOOOO...OOOOO.OOOOO..O.O.OOOO..O.OOOOOOO.O....O.
O.OO.O.....OOOOOOO.OOOOOOO.OO.O.OOOOOO.OOOOOO.OOOO..OOOOOO.OOOOOO..OOO
OOOO.OO.O.O.OO..OO.O..OOO.OOOOO.OOO..OOO...OO.OO..O.OO.OO.OO.OOOOO.O..
..OOOO.O..OOOOOOOO..OOO..O.OO.O.OOO.O.OOO.OO..OOOO.O.OOOO.O.OOOOOOOO.O
OOOOOOOOOOOO.OOO..OOOO.O.OOOO..OOOOOOO.OO.OOOOOOO.OOOOO...OOOOOO.OOO.O
OOO.O.OO....O...OOOO.OO..OOO..O.O.O...O.O.OO.O..OOOO.OOOOOOOOOOOO.OOO.
.OO.OOOOOO..OOOOOO.OOOOO..OO.OOOOOOOO.O.OO..OO.OOOOO.OOOOOOOO.OOOOOO.O
OO.OO..OO.OO.O.OOO..O...O..OO.O...O.O.O.O.OO..OO.OO.O...OOOO.OOO.O..O.
OO..O........OOO...OO.OOOOOOOO..OOO..O..OOO.OO.O.OO.OOO.OOOOOOO..OOOOO
.O..OOO...O.O.OO..O..OOOOOOOOOOOOOOO.OO....O.OOOOO...OOOOO.OOOOOO.OO..
OOO.O..OO.OOO.OOO.OOOO.OOO..OOO.O.OOOO..OOOOO.OOO.O.O...OOOOOOOOO.O...
.OOO.O..OOO.OO...OO.OOOOOOOOOO.O.OOOOOOO..OOO.O..OO.OOOO.O...OOOO....O
OO.OOOOO.OO.O.OO.OOOOO.OOOOOOOOOOOO...O.O.O...O.OOO.OOO.O..OO..OOOOO.O
OOO.O..OO..OOOO..OOOO...OO.O.OOOOOO..O..OO.OOOOO.OOOOOO.O.OOO..OOOO.OO
OOO.O.OOO....O.....O...OOOO..O.O.O.OOO.O.O.OO.OO.OO.O.O..O.OO...OO.OO.
OOO.OOO.OO.O.OO.O.O.O.O..O..OO..O..OOOO.OOOOO.OO.OOOO..OOO.O....OOOOO.
.OOOOOOO..OOO.OOOO.OO..O.O..OOOOOOOO.OO.OO.O...OOO..O.OO.OOOO.OOO.....
OOOO.OO.OOO.O.OOO...O.O..O.OOOOOOO.OOOOO.O.OO.O.OOOOO...OOOOO.OOOOOO.O
OOOO.OO..O..OO..OO.OOOOOOO.OOOOOOOOOO.OO....OOOOOOOOO.OOOO..OO..OOOOOO
O.OO.OO.OOO.O.OOO.OO...OOO.O.OOO.O.O.OOOO.O.OOO.O.O.OOO.OOOO.OO.OO.O.O
O..O.OOOOOOO..OO.OOO.OO..OOOO..O...O.OOOOO.OO......O..OOOO..OOOO..OOO.
.OOO.O.OOO.O...OO.OOOOO..O..OO.O.OO..OOOO.OOOO.OOO..OOOO..O...O...OOOO
O.OO.OOOO.O.OOOO.OO.OO..O..OO.OOOO.O.OOO.OOOOO.O.O.O.O.O.O.OO.OO.....O
.OO.OOO.O.OOOOOOOOOO.OOO..OO.O..OOOO...OOO.O.O.OOOO..O.OOOOOO..OOOOOO.
OO.OOOO.OOOOOO.OOOOOOOOO.OOO..OOOOOO.OOOO...OOOO.O..O..OOOOO.OOO.O.O..
O.OOO.O.OOO.O..OOOOOOOO.OOO..OO..OO..O...O....O.OOO.OO...OOOOO...OO..O
...OOOOOOOOO.O....OOOO.OOOOOO.OO.OO.OO...OO.OO..OO.O.OO.O.OOO.OOO.O...
.O..OOOOOOO..OO.OO..O.OOOOO.OOOOOOOOOOOOO.O.O.OOO.OO.OOOOO..OOOOOO..OO
O.OO....O....OOO.O.O..OO.O..OO...OOOOOOO.OOOOO.OOOO.O.O.OOOO.OOOOOOOO.
=> 1487
 

for 1s and . для 0 с для облегчения визуализации. Последние два корпуса имеют размеры 50×50 и 70×70 соответственно; В качестве эмпирической меры вашему решению не должно потребоваться более нескольких секунд для вычисления результата для этих входных данных (на типичном настольном компьютере менее секунды для быстрых языков; 70^4 ~ 24 миллиона). Но учтите, что возможность решить эти входные данные НЕ является гарантией правильного ответа; как упоминалось выше, вам необходимо объяснить, насколько ваш ответ соответствует временной сложности.

O

#код-гольф #код-гольф #сетка #ограниченная сложность #бинарная матрица #домино

Python 3.8 (предварительная версия), 544 байта

 
 
 ＷＳ⊞υιυＦＬυＦＬ§υι«Ｊκι¿⁼ＫＫO«≔⟦ω⟧θＷθ«≔Φurdl№⪪α¹⊟ＫＤ²✳μλ¿λ«≔§λ⁰λ✳λλ≔ＫＫηＰ§dlur⌕urdlλ¿⁼ηO≔⟦⟧θ«?✳η⊞θη⊞θＫＫ»»«≔⊟θλ¿λ«✳λ↧λ✳ＫＫ↧⊟θ»O»»ＵэＫＡ↥λ»»≔ΣＥRD№ＫＡιθ⎚Ｉθ
 
 
 

Попробуйте онлайн!

Представьте себе шахматный узор на сетке. Я применяю плохо разработанный алгоритм Хопкрофта–Карпа к двудольному графу, полученному соединением ñ4ñ3ñ1Ɗ=¥Ƈñ1‘$⁸;ⱮḢ;U$3ịḢ}⁺¦⁹$2¡Wʋ3¦ɼ$02ịñ3ß1ẸэƲэȯƊẸaŒḊ2ƑƲ¿Ẹ ịị®$} FJṁ×⁸Z,$ṖŻż"ḊƲ€Z,¥/Ẏ€;"/×¹Ƈ¥"ŒJ§ḂƊaFƊ0€,$ṫ-;1aL$,¬ȧ"Tɗʋ/;©$2ịḢç4ç3ç1=®ẈḢ¤ƊƇW;¹ƇƊƲ;ç1‘$Ṫ}Ḣ}¦;¹¹4?€ɼƲ®0;ç1$>/ƲэƲẠ¿ƊT€ṪçÐḟ3Ñ€Ʋṛ®ƲÐL3ịTLH s on "light squares" with those on "dark squares". A domino placement is a matching of this graph; the "maximum cardinality matching" found by the algorithm is the amount of dominos that can be placed.

В худшем случае есть ребра \$O(wh)\$ и вершины \$O(wh)\$, а Хопкрофт–Карп обещает быть \$O(E\sqrt{V})=O(w^ {1.5}h^{1.5})\$.

Желе, 216 199 байт

O

Попробуйте онлайн!

Полная программа, которая принимает двоичную матрицу и печатает целое число. При этом генерируется двудольный граф, а затем используется метод Хопкрофта-Карпа; он во многом основан на псевдокоде на странице Википедии, но, очевидно, должен соответствовать возможностям Jelly. Я думаю, что он должен соответствовать требованию сложности, поскольку базовый метод это делает и позволяет выполнить все задачи в общей сложности примерно за 28 секунд на TIO.

Древесный уголь, 140 байт

I=float('inf') def f(g,e=enumerate): a={(x,y):[(X,Y)for X,Y in[(x-1,y),(x+1,y),(x,y-1),(x,y+1)]if len(l)>X>-1<Y<len(g)!='O'==g[Y][X]]for y,l in e(g)for x,c in e(l)if'O'[:x+y&1]==c};R={};S={};D={};Q=[];m=0 def F(u): if not u:return 1 for v in a.get(u): if D[(p:=S.get(v))]==D[u]+1and F(p):S[v]=u;R[u]=v;return 1 while D.get(N:=None)!=I: for u in a:k=u in R;D[u]=[0,I][k];Q+=[u]*-~-k D[N]=I for u in Q: if D[u]<D[N]: for v in a[u]: if D[(p:=S.get(v))]==I:D[p]=D[u]+1;Q+=p, for u in a:m+=u not in R!=N!=F(u) return m

Попробуйте онлайн! Ссылка на подробную версию кода. Считает 197 домино за 5 секунд, а 721 за 30 секунд, что означает, что 1421 слишком медленный для TIO. Пояснение: По большей части это просто мой ответ на Можно ли сделать этот узор из домино? но два изменения заключаются в том, что код не аварийно завершает работу, когда ему не удается разместить домино, и он подсчитывает количество домино и выводит это как окончательный результат.