0
$\begingroup$

From this codegolf question.

Consider an $r$ by $c$ matrix of nonnegative integers, called $M$. You also have a zero matrix of the same dimensions, called $N$. A "move" consists of replacing a rectangle of numbers within $N$ with any positive nonzero integer.

Valid "moves":

2 moves:
0 0 0 0      0 0 0 0
0 2 0 0  =>  1 1 1 1
0 2 0 0      0 2 0 0
0 2 0 0      0 2 0 0

2 2 0 0
2 2 0 0
0 0 0 0
0 0 0 0

Invalid moves:

0 0 0 0
0 2 0 0
0 0 0 0
0 2 0 0

2nd move invalid:
2 2 2 0      2 2 2 0
2 2 2 0  =>  2 0 2 0
2 2 2 0      2 2 2 0

A few examples of valid $M$ matrices:

1 2 3 4 5
5 4 7 0 5

0 0 0 0
0 0 0 0

0

The question is, how do you find the minimum amount of moves required to recreate $M$ out of $N$?

$\endgroup$
  • $\begingroup$ Try A*. $\endgroup$ – D.W. Sep 9 '19 at 20:46
  • $\begingroup$ @D.W. I'll take a look. $\endgroup$ – girobuz Sep 9 '19 at 21:35

Your Answer

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

Browse other questions tagged or ask your own question.