Binary Matrix
Time limit2sMemory limit128 MB
Given a binary matrix, find and output the minimum sequence of flood-fill region flips that makes the whole matrix uniform.
Problem
You are given an n×m binary matrix. A binary matrix is a matrix whose cells contain only 0 or 1.
Define the operation Reverse(x, y) as follows. Let k be the value currently stored in cell (x, y). The operation finds the entire connected region of cells with value k that contains (x, y), using only up, down, left, and right adjacency, and changes every value in that region to 1-k. In other words, 0 becomes 1 and 1 becomes 0. Row and column numbers both start from 1.
Your goal is to use as few Reverse operations as possible so that every cell in the matrix has the same value, either all 0 or all 1.
Input
The first line contains two integers n and m. (1 ≤ n, m ≤ 100)
Each of the next n lines contains a length-m string made of 0s and 1s. The i-th of these lines represents the i-th row of the matrix.
Output
On the first line, print K, the minimum number of operations to call.
On each of the next K lines, print x and y for one operation, in order. A line means that Reverse(x, y) is called at that step.