Flipping the Grid Suppose a grid of size N * M is having only 1 and 0. 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).
Like suppose the initial grid with N=4 and M =3 is : 
101
110
101
000  
Now, if we choose x=3 and y=2, the new state of grid would be
011
000
011
000  
For a given state of grid, the aim of the game is to reduce the matrix to a state where all numbers are 1. What is minimum number of moves required?

Note that the order of flips does not matter, just the list of $(x,y)$ points that are the lower right corners of flips.  You might as well start from the lower right corner.  Flip $(N,M)$ if required.  Now check $(N-1,M)$ and $(N,M-1)$ and flip what is required.  Work your way up to $(1,1)$.  The worst case is a checkerboard with $0$ in $(N,M)$, which will force you to $NM$ flips.
