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 columns
in 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 a
counter 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 a
different 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-right
corners, checking for a '0', which can be a possible bottom-right or bottom-left corner
for a 2x2 block consisting of all zeros. Each of these matrix traversals are performed on
the 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 of
these 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!