Matrix filled with 0's and 1's

Question

A matrix of size $n \times m$ filled with $0$'s and $1$'s and this matrix is considered lucky if no two adjacent cell are same i.e.,( no adjacent two 0's or 1's together ) so, we can invert some cells i.e, (change 0 to 1 or 1 to 0) And after inverting k cells we've to find largest possible lucky sub- matrix of given matrix.

example given $8 \times 8$ matrix

8 8
00101010
00010101
10101010
01010101
10101010
01010101 
10101010
01010101



k= 1        answer= 7
k=2         answer= 8
k=0         answer= 6
k=1001      answer= 8

If we don't change the board, the best answer here is the 6x6 bottom right sub-board. We can invert cells (2,2) and (1,1) to get a better answer.

Answer 1

To fulfill your adjacency requirements a given matrix must have a checkerboard pattern, i.e. alternating $0$'s and $1$'s in both the rows and the columns. There are two ways this can be done. The first row could either start with "$0,1,0,1,\ldots$" or it could start with "$1,0,1,0,\ldots$".

A simple algorithm to solve your problem is the following:

Pick one of the two patterns, let's say the first one, and run through the matrix from top to bottom, marking elements that fit the pattern as Good (G) and and those that don't fit as Bad (B). I've made an example below:

It should be clear that those that are marked Bad would actually have been marked Good if the other pattern had been used.

Now run through the matrix with sub-matrices of every possible dimension, starting with the largest. For a given sub-matrix, count the number of G's and number of B's. Pick the smaller of those two numbers. That number will be the number of inversions (k) needed to make that sub-matrix a lucky sub-matrix. Keep track of the smallest number of inversions needed for each sub-matrix dimension. In the example above, the smallest number of inversions needed for a $5 \times 5$ matrix is for example $10$. When you reach a sub-matrix where the required number of inversions is $0$, stop searching. This sub-matrix is the answer to $k=0$.

To find the answers to $k \gt 0$, sort the results you kept track of, i.e. sub-matrix dimensions and their smallest k, according to largest number of elements and smallest k.

And you are done.

EDIT

Made a primitive implementation of the above algorithm. The results for the above example is the following ($x$ and $y$ are the dimensions of the sub-matrix):