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.
