Lights Off, Revisited!

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 jth number in the ith row represents the state of the lightbulb at coordinates (i,j): 0 if it is off, 1 if it is on. All coordinates are 0based, 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 i,j,c, where 0≤i,j<n are 0based coordinates of the lightbulb at the starting point (i stands for the row number, j stands for the column number), and c is one character from the set {N,E,W,S}, N meaning moving to smaller row coordinates, S to larger row coordinates, W to smaller column coordinates, and E to larger column 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 
Tags  admin 
Date Added:  15062009 
Time Limit:  6 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA, PYP3 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 