In the contest analysis it says: With this insight, we can implement a simpler backtracking algorithm that places mines row by row from top to bottom with non-increasing number of mines as we proceed to fill in the next row and prune if the configuration for the current row is invalid (it can be checked by clicking at the bottom right cell). ---
This pruning method doesn't actually work when we do the last-but-one row. When you fill the last-but-one-row, you should also fill the last row as well. On Thu, Jan 15, 2015 at 6:53 PM, aman taneja <[email protected]> wrote: > Hi, > I was trying the backtracking approach discussed in "Contest Analysis". > > What I am doing is - > Say, we take the 5th test case of sample input -> "10 10 82" . > I am filling each row with mines till either 1. I have remaining mines or > 2. i start getting a configuration where the solution is "Impossible". > > > 1. for each row starting from 0, filling each row with > min(remainingMines,numColumns) eg. min(82,10), > Thus we get 10 stars('*') in first row and 90 '.' in the below 9 rows. > Then check whether this configuration gives a valid solvable Game. > If not, then remove the bottom right-most filled '*' (backtrack and then > check if this is a valid configuration). Now, the rightmost column to which > the row could be filled changes to 'c-1'(if c was the previous column). > If this is not a valid configuration, I would again backtrack and remove 1 > more '*'(the new rightmost filled '*'), else I would add a new '*' to the > first index of next row. > > > In the above test case, 10 10 82, I would fill the first 8 rows > comfortably, then add 2 '*'s to the next(9th row). > Now, this config would give "Impossible" result(by floodfill algorithm). > Hence, I backtrack to 8 rows of '*' + 1 '*' in the 9th row.Now, this > config again gives "Impossible" answer. > Thus, I go further back to 80 '*'s. Now, the backtracking solution returns > to 'main' as I have reached the start of a row and have nowhere to go. > > > Code - > > > #include<iostream> > #include <fstream> > #include <cstdlib> > // for getch() > #include<stdio.h> > > // For clock time and time duration stats > #include <time.h> > > #include <map> > #include <vector> > #include <string> > #include <cstring> > > #include <set> > #include <algorithm> > #include <utility> > #include <list> > #include <queue> > #include <stack> > #include <limits.h> > #include <iomanip> > #include <math.h> > #include <cmath> > #include <assert.h> > #include <complex> > #include <valarray> > > using namespace std; > > > // Default For loop with variable name "i", first = 0, > increment = 1 > #define FOR_DEF(i, last) QL_FOR(i, 0, last, 1) > #define QL_FOR_DEF FOR_DEF > > // check whether indices in range of an array/matrix > #define in_bounds(x, y, r, c) (x < r && y < c && x >= 0 && y >= 0) > > typedef pair<int,int> p_ii_t; > typedef p_ii_t P_II; > > const int diff[]={-1,0,1}; > > bool noNeighborMine(int (*bc)[51],int R,int C,int p,int q){ > QL_FOR_DEF(i,3){ > QL_FOR_DEF(j,3){ > if( in_bounds(p+diff[i],q+diff[j],R,C) && > 2==bc[p+diff[i]][q+diff[j]]) > return false; > } > } > return true; > } > > bool openAllNeighbors(int (*bc)[51],int R,int C,int p,int q,int > &safe,queue<P_II> &qu){ > QL_FOR_DEF(i,3){ > QL_FOR_DEF(j,3){ > if( in_bounds(p+diff[i],q+diff[j],R,C) && > !bc[p+diff[i]][q+diff[j]]){ > --safe; > if(!safe) > return true; > bc[p+diff[i]][q+diff[j]]=1; > qu.push(MKP(p+diff[i],q+diff[j]) ); > } > } > } > return true; > } > /* board -> orig board > cr - current row > cc - current col, upto which the mines were filled in the last row. > Note that the mines would get filled in a non-increasing fashion. > Hence, the current col index can't exceed the one immediately before. > > R-> tot rows > C-> tot cols > safe -> no. of non-mine/valid places yet to be uncovered > */ > bool validConfig(int (*board)[51], int R,int C,int safe){ > if(2==board[R-1][C-1])return false; > // copy board current config for validation > int bc[51][51]; > QL_FOR_DEF(i,R){ > QL_FOR_DEF(j,C){ > bc[i][j]=board[i][j]; > } > } > > // apply flood-fill > queue<P_II> q; > > // clicked first block > q.push( MKP(R-1,C-1) ); > bc[R-1][C-1]=1; > --safe; > > while(!q.empty()){ > P_II p=q.front(); > q.pop(); > if(noNeighborMine(bc,R,C,p.first,p.second)) > openAllNeighbors(bc,R,C,p.first,p.second,safe,q); > if(!safe) > return true; > } > return false; > } > > void backtrack_mines(int (*board)[51],int R,int C, int cr,int cc,int > &safe,int &cnt){ > > // put at most 1 column of starts in the next row > cc=min(cnt,cc); > QL_FOR_DEF(i,cc)board[cr][i]=2; > > // safe places > safe-=cc; > /* Check validity of current config. > Backtrack, if not valid. > */ > while( !validConfig(board,R,C,safe) ){ > board[cr][cc-1]=0; > --cc; > ++safe; > if(!cc) > return; > } > > // remove 's' mines from the cnt. > cnt-=cc; > > if(!cnt||cr==R-1)return; > > backtrack_mines(board,R,C,cr+1,cc,safe,cnt); > } > > void reorderI(int &x, int& y){ > int xCopy, yCopy; > if (x < y){ > y = xCopy; > x = yCopy; > } > } > > int main(){ > #if PRINT_TIME > clock_t t = clock(); > #endif > > #if 01 > FILE *fIn = freopen("D:\\DUMP\\input.in", "r", stdin); > FILE *fOut = freopen("D:\\DUMP\\output.out", "w", stdout); > assert(fIn&&fOut); > #endif > int T = inpI(); > int tc=T; > int board[51][51]; > while (T--){ > int r=inpI(); > int c=inpI(); > int m=inpI(); > > swap(r,c); > /* 0 -> '.'(not opened, non-mine) > 1 -> 'c' > 2 -> '*'(mine, which would never get opened) > */ > QL_FOR_DEF(i,r){ > QL_FOR_DEF(j,c){ > board[i][j]=0; > } > } > int mc=m,nr=0,nc=0; > > /* > mc - mines count > */ > int safe=r*c; > backtrack_mines(board,r,c,0,c,safe,mc); > > // success > printf("Case #%d:\n",tc-T); > if(!mc){ > board[r-1][c-1]=1; > QL_FOR_DEF(i,r){ > QL_FOR_DEF(j,c){ > printf("%c",".c*"[board[i][j]]); > } > printf("\n"); > } > }else printf("Impossible\n"); > } > } > > -- > 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/c9ec25bf-f166-404b-94fe-cb186a0c2629%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/CAECKw-OYDbnvZ0LM4PeBTo7VVAsXEWfe%3DCNsx3dbmxHqOxkpEA%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
