My approach was somewhat similar, except I tried to place the mines in a rectangle instead of the empty squares.
First, I treated and Nx1 grid and any grid with 0,1,2, or 3 empty squares as special cases. This allowed me to know that I would always have a 2x2 rectangle empty in the corner. I then recognized that I could fill an (R-2)x(C-2) rectangle with mines and, as long as there were no gaps, the 2 "channels" formed by the empty rows/columns would always guarantee that it could be solved with 1 click. It would look like this (the Xs are squares I know to be blank due to my special casing) ***.. ***.. ***.. ...XX ...XX Then I just had to deal with the E extra mines that wouldn't fit in that rectangle. If E is even, then it is simple, just put pairs of mines in the "channels" as needed. If E is odd is is a bit more complicated. If you put a single mine in either of the "channels" you will have an impossible grid, but you can move the mine from the lower-right hand corner of the rectangle of mines (labelled C below) to form a pair. This works as long as the spaces labelled A below are empty. If they are not empty, the answer is impossible. ***.. ***.. **CAA ..AXX ..AXX so this is a possible grid with E = 7 and C being moved ***** ***** **... **.XX *C.XX I believe that last step means that any grid (with R and C at least 2) with 5 or 7 empty squares is impossible. On Sunday, April 13, 2014 6:06:03 PM UTC+9, ajlopez wrote: > My solution (but still with rejection in small dataset): > > > - In every solution, the empty cells could be moved to touch a side (that is, > if the empty cells is an "internal island", the same solution could be moved > to have an empty cell on a side "touching" the exterior) > > > > - Find a rectangle r x c, so empty cells == r x c or empty cells > r x c + 1 > > > - Put the empty rectangle with one corner in the board corner, named A. > > > > - Cleverly extend the rectangle, if needed, to have n cells, where n = empty > cells > > > - Click on the corner A > > > My code > https://github.com/ajlopez/TddRocks/tree/master/Gcj2014 > > > https://github.com/ajlopez/TddRocks/tree/master/Gcj2014/Minesweeper > > > > I put the empty rectangle at top left. The only problem with such approach, > the extending phase should contemplate extending to the right, and extending > to the bottom. I'm not sure if I can find the "biggest or more appropiate" > initial rectangle that can be extended only to the right. > > > > Angel "Java" Lopez > @ajlopez > > > > > > On Sun, Apr 13, 2014 at 3:20 AM, Mohamed Ghoneim <[email protected]> wrote: > > > This is wrong because of the last empty cell in the first column will never > get filled as there is no 0 surrounding it. > > > > > -- > > Mohamed Sayed Ghoneim > > > > > > On Sun, Apr 13, 2014 at 8:18 AM, Dhruva Sagar <[email protected]> wrote: > > > > I get the following : > > ***** > ....* > c...* > > > > > ....* > .**** > > > > > > On Sun, Apr 13, 2014 at 11:07 AM, Mohamed Ghoneim <[email protected]> wrote: > > > > > > > > What will you output for 5 5 12 ? > > > > > -- > > > > Mohamed Sayed Ghoneim > > > > > On Sun, Apr 13, 2014 at 7:32 AM, Dhruva Sagar <[email protected]> wrote: > > > > > The problem does not state anything about placing the mines so I assumed we > are free to choose that to try and get the optimal result. > > > > I decided to go with a spiral algorithm to place the mines until M mines are > placed, from there I went ahead to calculate the weights for each of the > remaining cells based on how many neighbors have mines and I selected the > first mine with weight 0 as 'c' if present, if not then the answer would be > impossible. > > > > > > > > > However my answer seems to be rejected so if someone would be kind enough to > throw some light on what I might be doing wrong it would be great! > > > > -- > > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > > > > > To post to this group, send email to [email protected]. > > To view this discussion on the web visit > https://groups.google.com/d/msgid/google-code/898c6f4b-1dca-499c-9af4-78126f3fe5f0%40googlegroups.com. > > > > > > > For more options, visit https://groups.google.com/d/optout. > > > > > > > > > -- > > You received this message because you are subscribed to a topic in the Google > Groups "Google Code Jam" group. > > To unsubscribe from this topic, visit > https://groups.google.com/d/topic/google-code/u8Zlclt-W6k/unsubscribe. > > To unsubscribe from this group and all its topics, send an email to > [email protected]. > > > To post to this group, send email to [email protected]. > > To view this discussion on the web visit > https://groups.google.com/d/msgid/google-code/CAGihN_kNuj3QfgXG9N4mxyXWgngr%2BrV3tkneHgJinq86D3L-Kg%40mail.gmail.com. > > > > > > > > > For more options, visit https://groups.google.com/d/optout. > > > > > > -- > > > Thanks & Regards,Dhruva Sagar > > g-talk : [email protected] > > > > > y! : [email protected] > github : github.com/dhruvasagar > work : [email protected] > > > > > > > ---------------------------- > Senior Ruby/Rails/Node.js Consultant > ActiveSphere > > > > > > > -- > > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > > To post to this group, send email to [email protected]. > > To view this discussion on the web visit > https://groups.google.com/d/msgid/google-code/CAAJXOCCN4B_2b1Pa1%2B8fLS5E0L%2BG0hoW3KrY-HGtXrY%3Dm4AzRw%40mail.gmail.com. > > > > > > For more options, visit https://groups.google.com/d/optout. > > > > > > > > > > -- > > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > > To post to this group, send email to [email protected]. > > To view this discussion on the web visit > https://groups.google.com/d/msgid/google-code/CAGihN_njrX__VDiJ7y3OTBSmSce%3DPzs5AK0ee_9n9nL36vOc4g%40mail.gmail.com. > > > > > For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/2eff93cd-9d39-47a7-9405-36d66455a19c%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
