# Minimum amount of rectangles to create a 2-dimensional matrix

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$$?

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