A domino mosaic
An artist lays a mosaic of dominoes over the dark part of a photograph. The photograph is divided into cells; a domino covers exactly two cells that share a side, both must be dark, and dominoes do not overlap. How many dominoes will fit?
Two tests are real photographs by the site's author, the same as in the article's mosaic: “Storm” and “Lake Issyk”, each cell being the average brightness of a 3 × 3 pixel square.
Input
The first line holds n and m (1 ≤ n, m ≤ 200), the number of rows and columns. Then n lines of m characters: . is a dark cell that may be covered, # a light cell that must not be covered.
Output
The largest number of dominoes.
Examples
Example 1
3 4 ..#. .... #...
4
Example 2
4 6 ..##.. .#..#. ..##.. ......
8
Limits
- Time · Python
- 8000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 10 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Colour the cells like a chessboard. What colours are the two cells under one domino?
2Hint 2
Is it enough to count the cells of each colour and take the smaller? Check on the second sample.
3The idea
A domino always covers one black and one white cell. So a tiling is a matching in a bipartite graph: black dark cells on the left, white ones on the right, an edge for sharing a side. The largest number of dominoes is the maximum matching, and the Hopcroft–Karp algorithm finds it.
4Walkthrough
Number the dark cells separately by colour, and for each black one make a list of neighbouring white ones, at most four. Then Hopcroft–Karp: a breadth-first search from all free black cells builds layers by the length of the alternating path, then a depth-first search along the layers finds many shortest augmenting paths with no common cells, and each is flipped, adding one domino.
The colour count gives only an upper bound. In the second sample there are 18 dark cells, nine black and nine white, but eight dominoes. On the left four white cells border only three black ones, on the right the other way round: four black ones border three white ones. On each side one cell stays unpaired however you lay the tiles. This is Hall's theorem; in the article such regions can be seen on the photograph by tapping a red cell.
A long corridor one cell wide (the seventh test) gives augmenting paths thousands of steps long: a recursive depth-first search in Python hits the recursion depth limit, so the stack is our own, a list.
4+Solution
5Complexity
O(E √V), where V ≤ 40,000 cells and E ≤ 4V adjacencies. The plain Kuhn's algorithm is O(V E) in the worst case; on these grids it also makes it in time, but more slowly.
6Common mistakes
- Counting colours. min(black, white) is the answer only for shapes without bottlenecks: the second, third, fourth and fifth tests.
- A greedy tiling. Putting a domino on the first free pair from left to right easily locks in lone cells.
- Recursion. A path can be as deep as half the cells: the seventh test.