For 5 5 4 my algorithm/code gives Case #1: c.... ..... ....* ....* ...**
On Sun, Apr 13, 2014 at 9:07 AM, Richard Braakman <[email protected]>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 > > I think you also need to consider solutions where the mines are in a > rectangle in the corner and the empty space surrounds it. Consider 5 5 4. > It has 21 empty cells, and there's not enough room to make a rectangle > except 4 * 5 which doesn't work because there is one left over. However > you can make it work like this: > > **... > **... > ..... > ..... > ....c > > My code ended up with eight different cases to consider. I have a hunch > there's a more elegant solution though :) I could have gotten rid of three > of the cases by rotating the problem (turning "tall" grids to "wide" grids > so that always columns >= rows), but that still leaves five. > > I had: > > The case of 1 free space (always ok) > The case of rows (or cols) == 1 (ok if there is at least 1 free space) > The case of 0, 2, or 3 free spaces (always impossible) > The case of finding a rectangle of free space that fits (with an extra > line of size 0 or size > 1) > The case of finding a rectangle of mines that fits, possibly with one > partially filled line (with at least 2 free rows and 2 free columns next > to it) > > > -- > 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/55870c43d447a20a8f06442fd617cf97.squirrel%40clueonic.net > . > 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/CAMs%2BDqJfzkXx1Ec3MP2Q%3DLzP03HuQnKa9TN5ArqfZJguBXkCmg%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
