Another approach, maybe simpler Let r rows, c columns. When r == 1, or c == 1, the solvable positions are already known.
Let r>=2, c>=2 Let m the number of mines If m > (r-2)*(c-2) it is solvable only if r*x - m is even, > 4 If m <= (r-2)*(c-2), then it is solvable (start with a (r-2)(c-2) rectangle full of mines, with one corner over one of the original corners, and then start to remove mines from the external border) Any counter-example? Angel "Java" Lopez @ajlopez On Mon, Apr 14, 2014 at 11:31 AM, Leopoldo Taravilse <[email protected]>wrote: > 1 1 1 is not a possible case, as m < R*C > > > On Mon, Apr 14, 2014 at 11:28 AM, Emil Maskovsky <[email protected] > > wrote: > >> Looks pretty complicated :) >> >> One problem I see right at the beginning: >> for 1 1 1 your solution returns c alhough it should return Impossible. >> >> The Minesweeper problem was the trickiest for me too, had 2 failed checks >> until I got it right (my problem was that I considered things like 1 3 2 as >> impossible, although it should be "c**"). >> >> >> Dne pondělí, 14. dubna 2014 15:58:49 UTC+2 Leopoldo Taravilse napsal(a): >> > I also couldn't solve this problem (I calculated by brute force the >> small case just for making sure I advance to the next round but I couldn't >> solve C-large because my solution wasn't accepted for C-small). >> > >> > >> > >> > >> > What I did was: >> > >> > >> > if R = 1 and C = 1 return "c" >> > else if R = 1 or C = 1 return something like "c...****" (or the >> transpose if C = 1) >> > else if m = R*C-1 then c in [0][0] and * everywere else >> > >> > >> > else if m = R*C - k with k in {2,3,5,7} return impossible >> > else if m%2 = (R*C)%2 fill the last R-2 rows with * until I get m times >> '*' and then from C-1 to to 0 fill with '*' in the first two rows until I >> get m times '*' >> > >> > >> > else if R = 2 or C = 2 return impossible >> > else fill the last R-3 rows until m * are reached then fill the first 3 >> rows until I get m * >> > >> > >> > This is my code in case anyone wants to read it and tell me what's >> wrong with it: >> > >> > >> > >> > >> > >> > char board[5][5]; >> > >> > >> > bool calc() >> > { >> > int m2 = m; >> > if(r==1&&c==1) >> > { >> > board[0][0] = 'c'; >> > >> > >> > return true; >> > } >> > if(c==1) >> > { >> > forn(i,r) >> > board[i][0] = '.'; >> > board[0][0] = 'c'; >> > int pos = r-1; >> > >> > >> > while(m2>0) >> > { >> > board[pos][0] = '*'; >> > m2--; >> > pos--; >> > } >> > return true; >> > } >> > >> > >> > if(r==1) >> > { >> > forn(i,c) >> > board[0][i] = '.'; >> > board[0][0] = 'c'; >> > int pos = c-1; >> > while(m2>0) >> > >> > >> > { >> > board[0][pos] = '*'; >> > m2--; >> > pos--; >> > } >> > return true; >> > } >> > int sz = r*c; >> > >> > >> > if(m == sz-1) >> > { >> > forn(i,r) >> > forn(j,c) >> > board[i][j] = '*'; >> > board[0][0] = 'c'; >> > return true; >> > >> > >> > } >> > if(m == sz-2 || m == sz-3 || m == sz-5 || m == sz-7) >> > return false; >> > if((sz-m)%2 == 0) >> > { >> > forn(i,r) >> > forn(j,c) >> > >> > >> > board[i][j] = '.'; >> > board[0][0] = 'c'; >> > int posx = r-1, posy = c-1; >> > while(m2>0) >> > { >> > board[posx][posy] = '*'; >> > >> > >> > m2--; >> > if(posx == 1 && m > 0) >> > { >> > board[posx-1][posy] = '*'; >> > m2--; >> > } >> > >> > >> > posy--; >> > if(posy==-1) >> > { >> > posx--; >> > posy = c-1; >> > } >> > } >> > return true; >> > >> > >> > } >> > else >> > { >> > if(r==2||c==2) >> > return false; >> > forn(i,r) >> > forn(j,c) >> > board[i][j] = '.'; >> > >> > >> > board[0][0] = 'c'; >> > int posx = r-1, posy = c-1; >> > while(m2>0) >> > { >> > board[posx][posy] = '*'; >> > m2--; >> > >> > >> > if(posx == 2 && m2 > 1) >> > { >> > board[posx-1][posy] = '*'; >> > board[posx-2][posy] = '*'; >> > m2-=2; >> > >> > >> > } >> > posy--; >> > if(posy==-1) >> > { >> > posx--; >> > posy = c-1; >> > } >> > } >> > >> > >> > return true; >> > } >> > } >> > >> > >> > >> > On Sun, Apr 13, 2014 at 8:26 AM, Leopoldo Salvo <[email protected]> >> wrote: >> > >> > >> > HI, >> > >> > >> > >> > I could not get this one to pass either, i still don't understand why, >> it must be the way i fill the board (I ran the actual recursion algorigthm >> on both failures and successes and checked the number of cells left to be >> revealed and they were consistent with my results) >> > >> > >> > >> > >> > >> > If R or C == 1 then it is always possible >> > >> > >> > >> > otherwise, i calculate a rectangle top left of the board with width C-2 >> and height R-2, i call that a buffer zone, as long as M fits in that buffer >> zone it is possible (I fill it column by column: from top to bottom and >> from left to right) >> > >> > >> > >> > >> > >> > If M > bufferzone then i start filling the rectangle underneath it, so >> at max 2 rows height, and at most C-2 columns width. In this area i say the >> board will be ok as long as the number of mines in this container is even. >> I fill this rectangle from top to bottom and from left to right. >> > >> > >> > >> > >> > >> > after this lower rectangle is filled, if there are more mines remaining >> i do the same thing with the rectangle right of the buffer zone (this is a >> rectangle with at most 2 columns and R-2 rows). I fill this from top to >> bottom, from left to right. As long as the number of mines in this >> rectangle is even, it is ok. >> > >> > >> > >> > >> > >> > at this point there could be at most 3 more mines (requirements say M < >> R*C. >> > >> > >> > >> > IF remaining = 3 then it is possible (all mines except the clicked c), >> otherwise it is impossible. >> > >> > >> > >> > I am still baffled why it didn't pass, there must be some corner case >> or the way i fill it is not correct, any ideas? >> > >> > >> > >> > I suppose ill have to just run the data set against one of the passed >> ones and compare >> > >> > >> > >> > >> > -- >> > >> > 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/e0086e83-64ae-47d6-a070-2c9ccc3fb602%40googlegroups.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/e53f8c26-0f1a-4455-921a-b409e07b26a5%40googlegroups.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/CA%2BE_-jQR81f5BJcpWUtidfVgBE4qSjr7wDbJ%3DD0Y8kNRwjbCNQ%40mail.gmail.com<https://groups.google.com/d/msgid/google-code/CA%2BE_-jQR81f5BJcpWUtidfVgBE4qSjr7wDbJ%3DD0Y8kNRwjbCNQ%40mail.gmail.com?utm_medium=email&utm_source=footer> > . > > 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%2BDqJUJq%2BUd61MYL_n-LoaOgv%3DYYeCC%2BbMswxFTC5aNJG7YA%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
