Many Left

All submissions for this problem are available.
The classical game of OneLeft is played as follows. Some pegs are placed on an NxN grid. Initially, at least one cell is empty and at least one contains a peg (each cell contains at most one peg). A move consists of jumping one peg over an adjacent peg to an empty cell, and removing the peg that was jumped over. Formally, if there is a peg in cell (x1, y1), and cell (x2, y2) is empty, and (x1x2, y1y2) is one of (0, 2), (0, 2), (2, 0), or (2, 0), and there is a peg in cell ((x1+x2)/2, (y1+y2)/2), then the peg in cell (x1, y1) may be moved to cell (x2, y2) and the peg in cell ((x1+x2)/2, (y1+y2)/2) removed. The coordinate (0, 0) indicates the topleft corner, (N1, 0) indicates the topright corner, (0, N1) indicates the bottomleft corner, and (N1, N1) indicates the bottomright corner.
The game continues until no more moves are possible. Normally the goal of OneLeft is to leave a single peg on the grid. However, in this problem the goal is to leave as many pegs as possible. Optimal solutions are not required, but solutions that leave more pegs will score more points.
Input
Input begins with an integer N, the size of the grid. N lines follow with N characters each, representing the grid. A '.' character indicates an empty cell, and a '*' character indicates a peg.
Output
For each test case, first output the number of moves in your solution. Then output each move in the form "x1 y1 x2 y2", which indicates a peg moving from (x1,y1) to (x2,y2). Any whitespace in your solution will be ignored.
Scoring
Your score for each test case is the fraction of cells containing pegs after performing the moves in your solution. Your overall score is the average of your scores on the individual test cases. Invalid solutions will be judged as "wrong answer". In particular, if any legal moves exist after the moves in your solution have been performed, your solution will considered invalid.
Sample Input 1
6
..*..*
*..*.*
***.**
.***..
****..
**.*.*
Sample Output 1
13 1 3 1 1 3 3 1 3 0 5 0 3 0 2 0 0 3 5 3 3 5 2 3 2 5 0 5 2 3 2 3 0 2 4 0 4 0 3 0 5 3 0 1 0 0 0 2 0 0 5 2 5
Sample Input 2
5
.*.*.
..*..
*...*
...*.
.*...
Sample Output 2
0
The first sample output scores 8/36 = 0.2222.
The second sample output scores 7/25 = 0.28.
Recall that the goal is to maximize your score.
Test Case Generation
For each official test file, N is chosen randomly and uniformly between 10 and 30, inclusive. A real number D is chosen randomly and uniformly between 0.5 and 0.95, then each cell is independently chosen to contain a peg with probability D.
Author:  pieguy 
Tester:  laycurse 
Editorial  http://discuss.codechef.com/problems/MANYLEFT 
Tags  challenge nov12 optimization pieguy search 
Date Added:  30092012 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.4, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions