Lights Off, Revisited!Problem code: EX |
All submissions for this problem are available.
Johnny is, by now, a little bored of the original Lights Off game, and he has proposed his own variant. This time, the task which awaits him is much, much harder...Imagine we have a large square board, containing an n x n grid (matrix) of lightbulbs. Initially, some of them are on, and the rest are off. We can perform some special operations on the whole matrix, and we would like to switch off as many lightbulbs as possible. At each step, the only operation we can perform is defined as follows: we choose one particular lightbulb, one direction (North, East, West, or South), and starting from this lightbulb and going in the specified direction, till the end of matrix, one by one, we toggle the states of the lightbulbs - from on to off, or from off to on.
Input
First, 1 n 1000, the size of the board. Then n rows of n numbers follow, representing the initial state of the lightbulbs, where the j-th number in the i-th row represents the state of the lightbulb at coordinates (i,j): 0 if it is off, 1 if it is on. All coordinates are 0-based, i.e., the bulb in the top left hand corner has coordinates (0,0).
Output
First, you should output k, the number of operations you perform. The following k rows should describe a sequence of operations to be performed on the board, in the order in which they should be applied. Each operation is described by three space separated numbers x,y,c, where 0 x,y<n are 0-based coordinates of the lightbulb at the starting point, and c is one character from the set {N,E,W,S}, N meaning moving to smaller y coordinates, S to larger y coordinates, W to smaller x coordinates, and E to larger x coordinates.
Scoring
For each lightbulb than remains on after all the operations, you will receive one penalty point. For each operation performed you will receive one penalty point.
The total score is averaged over 9 data sets.
Example
Input:
3
1 1 1
1 1 1
1 1 1
Output:
2
0 0 E
0 0 S
Score:
7
| Author: | admin |
| Date Added: | 15-06-2009 |
| Time Limit: | 6 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
Is the decimal score that we receive the number of penalty points we receive, averaged over all the test sets? If so, then shouldn't lower scores be better?
Just to clarify, (since the example doesn't help) if I have:
1 0 1 1
1 0 0 0
0 1 1 1
1 0 1 0
And I perform 1 2 E, what would I get?
From the problem statement I think that it would be:
1 0 1 1
1 0 0 0
0 0* 0* 0*
1 0 1 0
where * = toggled
Is this correct?