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.
Input
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.
Output
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 spaceseparated numbers i and j. Each individual line commands the singer to
step on the ith tile of the jth 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".
Example
Sample input
4 3 0111 1010 1000 0 0Sample output
3 1 2 1 3 4 3
hide comments
tieuchanlong:
20160506 19:21:16
Why I have a NZEC??


DragonBorN:
20150421 00:05:11
Too much shit in this ques.. Such questions should be banned! 

Kshitij Korde:
20141212 22:11:49
To save numerous 'WA's


ISHANI:
20141003 11:24:44
Here no need for minimum number of step.


ISHANI:
20141001 11:26:26
Awsm problem.


Jakub Stanecki:
20140211 02:15:48
AC after adding swap(n, m); and replacing printf("%d %d", i, j); with printf("%d %d", j, i); 

Taym:
20130524 21:20:59
Finally Accepted :) Last edit: 20130525 07:23:56 

15972125841321:
20120615 16:46:14
can u plz tell me wher i m getting wa...


:D:
20120521 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:
20120520 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 
Date:  20040701 
Time limit:  2.400s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Swiss Olympiad in Informatics 2004 