I am trying to solve the following problem:Given a matrix which consists of only 0's and 1's. Considering the matrix as a metal sheet, we need to cut-out square blocks of sizes 2x2 consisting of only 0's from it. A 1 in the sheet (represented by the matrix) indicates that we cannot cut the region out from the sheet. Given such a matrix, find the maximum number of blocks which can be extracted.For instance, if the given matrix is:There can be 2 blocks which can be extracted out of this.My Solution:I am using a greedy algorithm to solve the problem. I traverse from all the corners of the matrix (top-left, top-right, bottom-left, bottom-right) - one by one, extracting out the blocks on a first encountered first extracted basis. Finally I return the maximum of the 4 values that I get. From each corner, I traverse an entire row first (horizontally), only then I move up or down in the matrix.The algorithm is as follows:1) Starting from the top-left corner of the matrix (0,0), I iterate along all the columnsin this row from left to right. 2) If a zero is encountered at a position (i,j), I check if this is a possible contender to be the top-left corner of a 2x2 block consisting of all zeros -which would be the case when values at (i, j+1), (i+1, j) and (i+1, j+1) are all zeros.3) If it is, I fill the 2x2 block {(i,j), {i,j+1), (i+1,j), (i+1,j+1)} with 1's, and acounter is incremented.4) Steps 2 through 3 are repeated for all rows from the top to bottom.5) I restore the original matrix in the problem, and start again from the top-right corner of the matrix (0, N) - N being the number of columns in the matrix, and iterate along all the columns in this row, from right to left.6) If a zero is encountered at a position (i,j), I check if this is a possible contender to be the top-right corner of a 2x2 block consisting of all zeros - which would be the case when values at (i, j-1), (i+1, j) and (i+1, j-1) are all zeros.7) If it is, I fill the 2x2 block {(i,j), {i,j-1), (i+1,j), (i+1,j-1)} with 1's, and adifferent counter is incremented.8) Steps 6 through 7 are repeated for all rows from the top to bottom.9) Likewise, the matrix is traversed two more times from bottom-left and bottom-rightcorners, checking for a '0', which can be a possible bottom-right or bottom-left cornerfor a 2x2 block consisting of all zeros. Each of these matrix traversals are performed onthe original matrix given in the problem - i.e. changes made in top-left traversal are discarded while traversing the matrix from top-right and so on.10) The 4 traversals of the matrix give us 4 different counters, and the maximum ofthese 4 values is returned as the result.So far I have not been able to come with a test case which shows that the algorithm is incorrect. As I am not very good with proving correctness of algorithms, I need some help to figure out if this algorithm is correct.Thanks!
Correctness of the greedy algorithm
algorithms;correctness proof;greedy algorithms
If I am right, the configuration below leads to a 7 blocks greedy solution (on the left). By symmetry, all four directions.But there is an 8 blocks solution (on the right).The problem with a greedy approach is that consuming a block can destroy two other possible blocks, and have a negative impact.Repeating the search in different directions will not fix this, as it is possible to build symmetric patterns that result to the same behavior in all directions.