Original link: https://www.shuizilong.com/house/archives/dmopc-22-contest-5-p5-twos-and-threes/
Question: Given a board with obstacles, ask whether it can be perfectly covered by L-shaped dominoes of 1×2, 1×3, and length 3.
Analysis: First weaken the problem, consider that if there are only dominoes, then judging whether it can be filled only needs bipartite graph matching. Further, if we consider L-shape, we can use network flow modeling, refer to this question . So the basic idea might be some kind of network stream?
It seems to be true, each point is connected to at least 1, and at most 2, so the upper and lower bound network flow is enough.
This article is transferred from: https://www.shuizilong.com/house/archives/dmopc-22-contest-5-p5-twos-and-threes/
This site is only for collection, and the copyright belongs to the original author.