DFLOOR - Dance Floor

You recently watched a video clip in which a singer danced on a grid of colourful tiles enlightened from below. Each step on a tile flipped the tile's state, i.e. light on or off. In addition to that, all the neighbouring tiles flipped their states, too.

In this task, you are supposed to come up with a short program that decides if it is possible for the singer to switch on the lights of all the tiles, provided that he dances on the appropriate tiles.

The dance floor has rectangular shape. At the beginning, some of the tiles are already alight. Your program may temporarily switch off some tiles, if it deems that necessary to reach its goal. Stepping on a tile toggles its own state as well as the states of the four neighbouring tiles directly above, below, to the left and to the right. Of course, in the case of a peripheral tile, there will be only three or two neighbouring tiles.

Here comes an example:

If the dancer steps on the tile indicated by the brown shoe, all the tiles within the white area change their states. The resulting dance floor is depicted on the right.

You may assume that the singer is fit enough to jump from any tile to any other tile, even if the destination tile lies on the opposite side of the dance floor.


There are several test cases. The first line of each case contains two integer numbers x and y, indicating the width and the height of the dance floor grid. The numbers are separated by a single space and satisfy 3 ≤ x,y ≤ 15.

The following y lines containing xcharacters each describe the initial on/off states of the tiles. A zero means "the tile is switched off", a one digit means "the tile is alight".

Input ends with 0 0.


For each test case your program should output the number of steps needed to switch all the lights on, followed by exactly that many lines with two space-separated numbers i and j. Each individual line commands the singer to step on the i-th tile of the j-th row. Starting with the situation of the input file and executing all the commands in the output file, all the tiles must be switched on.

If more than one solution exist, your program should output an arbitrary one of them. If, on the other hand, no solution exists, your program should write the number "-1".


Sample input

4 3 0111 1010 1000 0 0

Sample output

3 1 2 1 3 4 3

hide comments
tieuchanlong: 2016-05-06 19:21:16

Why I have a NZEC??

DragonBorN: 2015-04-21 00:05:11

Too much shit in this ques.. Such questions should be banned!

Kshitij Korde: 2014-12-12 22:11:49

To save numerous 'WA's
a) The 0 and 1's on Dance Floor are not space separated.
b) If answer is -1, print it with EOL.

ISHANI: 2014-10-03 11:24:44

Here no need for minimum number of step.
if u want to do so,check it->http://www.spoj.com/problems/CERC07B/

ISHANI: 2014-10-01 11:26:26

Awsm problem.
Nice feeling after solving it

Jakub Stanecki: 2014-02-11 02:15:48

AC after adding swap(n, m); and replacing printf("%d %d", i, j); with printf("%d %d", j, i);

Taym: 2013-05-24 21:20:59

Finally Accepted :)

Last edit: 2013-05-25 07:23:56
15972125841321: 2012-06-15 16:46:14

can u plz tell me wher i m getting wa...
my sub id is 7155392
i got the same accepted without the steps at CERC07

Last edit: 2012-06-15 16:49:35
:D: 2012-05-21 06:06:39

I'm not sure, but I think minimal is also the only solution if you don't step on the same fields twice. Still, if I understand my code correctly, I double checked for the minimal.

15972125841321: 2012-05-20 23:15:09

do we have to output the minimum number of steps with its solution or all the possible solutions with their steps??

Added by:MichaƂ Czuczman
Time limit:2.400s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Resource:Swiss Olympiad in Informatics 2004