master - Any other solutions to the MineSweeperMaster in Google code jam 2014 qualification round? -

below solution, solves problem. hope can see solutions uses dynamic programming or other algorithms (except brute force) try put 0 cells board.

below steps of algorithm:

 set remains = r * c - m. 

1) m = 0: free spaces. print "." in cells , overwrite cell "c".

2) remains = 1: same idea, . print "*" in cells , overwrite cell "c".

3) if r==1, or c==1: solution put "*" in first m cells, , "c" in last cell, other cells "."

(exchanged position of case 4) , 5). comments @thecomputerguy.) 4) in other cases, if remains 2, 3, 5, 7, "impossible". else:

5) if r==2, or c==2: if m % 2==0, have solution: in first m/2 columns or rows "*", , "c" in last cell, other cells "." if m % 2 == 1, "impossible".

6) fill mines (0,0), line line, left right, down. need consider special cases: set rs = m / c; cs = m % c 6.1) if rs < r - 2, , cs < c - 1, filled, , put "c" in last cell, other cells "."

 ********** ********** ********** ********** ****...... .......... .......... 

6.2) if rs < r -3, , cs == c -1, move 1 mine start of next line. (this case)

 ********** ********** ********** *********.(not work here) .......... .......... .......... (final solution) ********** ********** ********** ********..(move * next row , put space here) *......... .......... .........c 

6.3) if rs == r - 3, , cs == c -1, move 2 mines start of 2 lines

 ********** ********** ********** *********.(not work here) .......... .......... (final solution) ********** ********** ********** *******...(move * next row , put space here) *......... *........c 

6.4) if rs >= r - 2, , remains % 2 == 0 leave first remains/2 columns of first 2 rows empty , fill other cells mines:

 c...****** ....****** ********** ********** 

6.5) if rs >= r - 2, , remains % 2 == 1, leave first (remains -3)/2 columns of first 2 rows empty, , first 3 columns of 3rd row empty, , fill other cells mines:

 c...****** ....****** ...******* ********** 

now conditions can covered.

i new system. hope credits if solution. , welcome post solutions. thank much!

(posting here because don't have 10 rep. other one)

my solution:

1. if m = r * c - 1, fill grid mines; else:
2. recursively "simplify" grid filling last row / column - smallest of 2 - mines (while have mines enough that).
3. put rest of mines in final "simplified" grid, in sequence, starting bottom-right. constraint here can't leave single empty cell between mine , border.
4. click on (0,0).

the c code here.