Hacker Earth question similar to flipcoins

Recently in Hacker Earth’s Angel prime hiring challenge there is a question which is similar to flipcoins but Im unable get a working algorithm please help me . I dont need the code just give me a basic idea of how we can solve that.

Thanks in Advance

Problem Statement :

Flip the world is a game. In this game a matrix of size N*M is given, which consists of numbers. Each number can be 1 or 0 only. The rows are numbered from 1 to N, and the columns are numbered from 1 to M.

Following steps can be called as a single move.

Select two integers x,y (1<=x<=N and 1<=y<=M) i.e. one square on the matrix.

All the integers in the rectangle denoted by (1,1) and (x,y) i.e. rectangle having top-left and bottom-right points as (1,1) and (x,y) are toggled(1 is made 0 and 0 is made 1).

For example, in this matrix (N=4 and M=3)





if we choose x=3 and y=2, the new state of matrix would be





For a given state of matrix, aim of the game is to reduce the matrix to a state where all numbers are 1. What is minimum number of moves required.


First line contains T, the number of testcases. Each testcase consists of two space-seperated integers denoting N,M. Each of the next N lines contains string of size M denoting each row of the matrix. Each element is either 0 or 1.


For each testcase, print the minimum required moves.


1 <= T <= 30

1 <= N <= 20

1 <= M <= 20

Sample Input (Plaintext Link)

5 5






Sample Output (Plaintext Link)



In one move we can choose 3,3 to make the whole matrix consisting of only 1s.

Time limit 3 sec(s)

Memory limit 256 MB

Source limit 1024 KB

It’s based on greedy paradigm not dynamic paradigm, just traverse from bottom to top because if
you toggle (1,1) to (x,y) then if you further move to (x+1,y+1) then (1,1) to (x,y) automatically toggle, so count number of zeroes from bottom to top manner, toggle the rectangle from (1,1) to (i,j) where m[i][j]=0
and move up till you reach the top left of the matrix.
But time complexity - N^2 * M^2.
if anybody have better sol, just tell me!

atleast a clue please