# How to find the maximum number of square groups in a board

I'm stuck with the following problem:
Given an n*m board, find the maximum number of square groups that can be positioned on the board.
What are square groups?

• They contain 4 distinct squares named: a, b, c, d
• a should be the neighbor of b
• b should be the neighbor of c
• c should be the neighbor of d
• Two squares are considered neighbors if they are adjacent to each other vertically or horizontally but not diagonally.
• Each square can belong to only one square group

I guess the problem should be handled by max flow network algorithms but I don't know how to model it to a graph.
Any help would be appreciated.

EDIT:
The answer is ⌊mn/4⌋, but we need to prove it with Max Flow Network.

• Isn't answer always $\lfloor mn/4\rfloor$? Dec 23 '21 at 17:22
• @InuyashaYagami Thanks for your comment. I edited the problem expectation. Dec 25 '21 at 12:36
• (Tetris shapes) Dec 25 '21 at 12:37
• @greybeard Not all the Tetris shapes satisfy the constraints. Dec 25 '21 at 14:38
• There's no connection to network flow... Dec 25 '21 at 15:04

First of all, since each square consists of $$4$$ cells and an $$n \times m$$ matrix contains $$nm$$ cells, you can clearly fit at most $$\lfloor nm/4 \rfloor$$ many different cells.

If $$n,m$$ are both even, then you can fit $$nm/4$$ different square-shaped squares. In all other cases, you have to be more cunning. I won't ruin the joy of the puzzle by explaining how to handle the other cases.