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 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".
Example
Sample input
4 3 0111 1010 1000 0 0Sample output
3 1 2 1 3 4 3
hide comments
majid:
2022-03-04 18:51:17
Warning: Read & Print \r\n after Each test case. |
|
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
|
|
ISHANI:
2014-10-03 11:24:44
Here no need for minimum number of step.
|
|
ISHANI:
2014-10-01 11:26:26
Awsm problem.
|
|
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...
|
|
: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. |
Added by: | MichaĆ Czuczman |
Date: | 2004-07-01 |
Time limit: | 2.400s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |
Resource: | Swiss Olympiad in Informatics 2004 |