0
$\begingroup$

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.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.