How many dominoes can you fit here?

Question

Much harder than Can this pattern be made with dominoes?

Challenge

A grid of width \$w\$ and height \$h\$ is given, filled with 1s and 0s. You can place a domino somewhere on the grid only if both cells are 1. You cannot overlap dominoes. What is the maximum number of dominoes you can fit in the given grid?

The worst-case time complexity should be \$\mathcal{O}(w^2h^2)\$ or lower. Please include an explanation of how your answer meets this time complexity requirement. If you use a built-in to solve the problem, you should provide an evidence that the built-in meets the time complexity bound. (Note that "being polynomial-time" is not sufficient.)

At least two well-known algorithms can be used to meet the bound: Ford-Fulkerson and Hopcroft-Karp. More specialized algorithms with even better runtimes also exist.

You may use any two consistent values in place of 1 and 0 in the input. You may assume that \$w\$ and \$h\$ are positive, and the input grid is rectangular.

Standard code-golf rules apply. The shortest code in bytes wins.

Test cases

The test cases use O for 1s and . for 0s for easier visualization. The last two cases are of sizes 50×50 and 70×70 respectively; as an empirical measure, your solution should not take more than a few seconds to compute the result for these inputs (on a typical desktop machine, less than a second for fast languages; 70^4 ~ 24 million). But note that being able to solve these inputs is NOT a guarantee of being a valid answer here; as mentioned above, you need to explain how your answer meets the time complexity bound.

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

Answer 1

Python 3.8 (pre-release), 544 bytes

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

Try it online!

Picture a checkerboard pattern on the grid. I apply a poorly-golfed Hopcroft–Karp to the bipartite graph obtained by connecting Os 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.

In the worst case, there are \$O(wh)\$ edges and \$O(wh)\$ vertices, and Hopcroft–Karp promises to be \$O(E\sqrt{V})=O(w^{1.5}h^{1.5})\$.

Answer 2

Jelly, 216 199 bytes

ñ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

Try it online!

A full program that takes a binary matrix and prints an integer. This generates a bipartite graph and then uses the Hopcroft-Karp method; it’s loosely based on the pseudo code on the Wikipedia page, but obviously has to stick within what’s possible in Jelly. I think it should meet the complexity requirement since the underlying method does, and manages to complete all challenges within about 28 seconds total on TIO.

Answer 3

Charcoal, 140 bytes

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

Try it online! Link is to verbose version of code. Counts the 197 dominoes in 5 seconds and the 721 in 30 seconds which means that the 1421 is just too slow for TIO. Explanation: Most of this is simply my answer to Can this pattern be made with dominoes? but the two changes are that the code doesn't crash when it fails to place a domino and it counts the number of dominoes and outputs that as the final result.