Chess Board

Question

There's an N X M board which filled with black and white chesses.

In each move, the player can flip one of these N X M chesses, meanwhile some chesses of its 8 neighbors will switch into its opposite color(from black to white and from white to black).

Here's four change pattern of the flip operation:

1. .*.

   • * ('*' denotes the position which will change its color, '.' denotes that the color will stay the same.) .*. It means the chesses of the choosen position's up, down, left and right will switch its color. (Don't forgot the chess which the player choose, it'll also switch its color.)

2. **.

   • * *.. It means the chesses of its upper-left, up, left, right and bottom-left will switch its color.

3. .**

   • * .*. It means the chesses of its up, upper-right, left, right and down will switch its color.

4. .**

   • . .** It means the chesses of its up, upper-right, left, down and bottom-right will switch its color. At the beginning, the player should choose one of these four patterns to flip (the player can only use one pattern in a single game), then try to switch the board into all white. By the way, we want to find a solution with minimal number of operations, if ties, select the smaller index of pattern.

Input

There are multiple test cases (no more than 150).

The first line of each case contains two integer numbers N and M (1 <= N, M <= 15), indicating the width and the height of the board.

The following N lines containing M characters each describe the initial state of the board. '0' and '1' correspond to white and black, respectively.
Input ends with 0 0.

Output

For each test case output the optimal solution, the pattern should be choosen follows by the minimal number of operations.

If none of these four pattern can switch the board into all white, output "Impossible" for the test case.

Sample Input

1 1
1
3 2
11
10
11
5 5
00000
00110
01110
00100
00000
0 0
Sample Output

1 1
4 1
3 1

Answer 1

https://www.2cto.com/kf/201609/546732.html