Matrices Generated Using Rectangles

Input is an r by c matrix of non-negative integers (you may input r and c as other parameters if this helps with golf). This may be inputted as a 2D array or, if you prefer, a 1D array (though taking in r this time is necessary). Strings separated by spaces to distinguish rows and newlines to distinguish columns are also fine (below, the test cases have multiple spaces to distinguish rows for clarity -- you do not have to do this).

Consider a matrix of zeros. A move consists of replacing a rectangle of numbers with a rectangle of some positive integer (not zero). For example, these are all valid first moves:

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

0 3 0 0
0 3 0 0
0 3 0 0
0 3 0 0

1 1 1 0
1 1 1 0
0 0 0 0
0 0 0 0


These are not valid first moves:

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

0 1 0 0
0 2 0 0
0 0 0 0
0 0 0 0

0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0


Make golfed code to answer the following the question:

Given an r by c matrix, what is the smallest possible number of turns taken to construct this?

Test Cases:

1 1 1 1
1 2 2 2
1 2 3 3
1 2 3 4
1 2 3 4
> 4

1  2  3  4  5
6  7  8  9  10
11 12 13 14 15
> 15

3 3 3 3 3 3
3 2 2 2 2 3
3 2 1 1 2 3
3 2 1 1 2 3
3 2 2 2 2 3
3 3 3 3 3 3
> 3

1 1 1 1 1 1
1 2 2 2 2 1
1 2 0 0 2 1
1 2 0 0 2 1
1 2 2 2 2 1
1 1 1 1 1 1
> 8

0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
> 0

1 1 1 1
1 3 3 1
2 3 3 2
2 2 2 4
> 4

• This seems like a very, very hard problem to compute efficiently to me. – orlp Jan 27 '18 at 15:03
• This is a harder variation of this challenge. – Arnauld Jan 29 '18 at 9:26
• Based on your examples of first moves I guess the numbers aren't inputted in order? None of your test cases reflect that, though. The test cases all go from 1 upwards (first test case four movies: 1,2,3,4; second test case 15 moves: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15; third test case 3 moves: 1,2,3; fourth test case 8 moves: 1,1,1,1,2,2,2,2). (It does make the challenge easier if only the same or next numbers can be inputted in that order. But if that's not your intention, you could for example swap the 1s and 3s in the third test case to reflect this.) – Kevin Cruijssen Mar 2 '18 at 8:18
• @KevinCruijssen That's not my intention. Fixed. – 0WJYxW9FMN Mar 2 '18 at 23:01
• What is the answer for [[1,1,1,1], [1,3,3,1], [2,3,3,2], [2,2,2,3]]? (In other words, can a rectangle be placed over different numbers?) – Peter Kagey Mar 23 at 17:06