Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

You are at a 12 story building called ECE Bhaban. You have just entered into a lift which has took you to a mysterious floor, Floor no. 20. In fact, you have got stuck into the lift and there is no way out of it except unlocking a Mysterious Lock. In order to unlock it, you have to solve a Puzzle.

The puzzle consists of a Binary Matrix of dimension $N \times M$. A binary Matrix has 0 or 1 in each of it’s cells and it’s called Beautiful when each of its rows has an odd number of ones and each of its columns has an even number of ones.

Now, to unlock the mysterious lock, you have to transform the given matrix into a Beautiful one. In one move, you can flip any cell value of the matrix (flipping a value means, if there is a $0$, after the move there will be a $1$, and vice versa). But the time is short, you are suffocating inside the lift. So, you have to do it with a $Minimum$ number of moves or report if it’s impossible to unlock the mysterious lock.

The rows are numbered from $1$ to $N$ (top to bottom) and the columns are numbered from $1$ to $M$ (left to right).

You have to print the minimum number of moves required to unlock the lock and the corresponding moves. If there are multiple solution, you can print any of them. If there is no solution, print “-1” (without quotes).

The first line of input consists of two space separated integers $N$ and $M$ ($1 \leq N, M \leq 1000$), representing the number of rows and the number of columns of the matrix respectively.

Next $N$ line contains $M$ characters each (each of which is either 0 or 1) representing the rows of the matrix.

The first line of output will contain a single integer $K$, the minimum number of moves required to unlock the lock or “-1” (without quotes) if it’s impossible to unlock.

If it’s possible to solve the puzzle, then next $K$ lines will print the moves. It will contain two space separated integers each, representing the co-ordinate of the cell which has been flipped on that move.

The output format will be of this form:

$K$

$X_{1}$ $Y_{1}$

$X_{2}$ $Y_{2}$

…

$X_{k}$ $Y_{k}$

here $X_{i}$ and $Y_{i}$ represents the row index of the cell (from top) and column index of the cell (from left) respectively.

($1 \leq X_{i} \leq N, 1 \leq Y_{i} \leq M$)

It is guaranteed that if there is a solution, then the number of moves of the solution will not exceed N x M.

Input | Output |
---|---|

4 3 101 011 100 110 | 3 1 1 2 1 4 1 |

After applying the 3 moves from output, the resultant matrix looks like this-
number of ones in rows are respectively 1, 3, 1, 1. All these values are odd. number of ones in columns are respectively 2, 2, 2. All these values are even. |

Input | Output |
---|---|

1 2 01 | -1 |

There is no way to make this matrix beautiful. |

73% Solution Ratio

Zobayer_AbedinEarliest,

nh_nayeemFastest, 0.0s

Zobayer_AbedinLightest, 131 kB

Zobayer_AbedinShortest, 1033B

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.