Queens on a Board Solution (InterviewStreet CodeSprint Fall 2011)
Created
October 13, 2011 19:02
-
-
Save yuvipanda/1285170 to your computer and use it in GitHub Desktop.
Queens on a Board Solution (InterviewStreet CodeSprint Fall 2011)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include<stdio.h> | |
#include<string.h> | |
#define MOD 1000000007 | |
int n,m,bit[1 << 10] ; | |
char g[52][52] ; | |
int memo2[1 << 15] ; | |
int spread(int mask) | |
{ | |
if(memo2[mask] != -1) return memo2[mask] ; | |
int nmask = 0 ; | |
for(int i = 0;i < m;i++) | |
{ | |
if(mask & 1 << 3 * i) if(i > 0) nmask |= 1 << 3 * i - 3 ; | |
if(mask & 1 << 3 * i + 1) nmask |= 1 << 3 * i + 1 ; | |
if(mask & 1 << 3 * i + 2) if(i + 1 < m) nmask |= 1 << 3 * i + 5 ; | |
} | |
return memo2[mask] = nmask ; | |
} | |
int good[50][1 << 8],szg[50],block[50] ; | |
int memo[50][1 << 15] ; | |
int solve(int x,int mask) | |
{ | |
if(x == n) return 1 ; | |
mask &= ~block[x] ; | |
if(memo[x][mask] != -1) return memo[x][mask] ; | |
int ret = 0 ; | |
for(int i = 0;i < szg[x];i++) if(!(good[x][i] & mask)) | |
{ | |
int cret = solve(x + 1,spread(good[x][i] | mask)) ; | |
ret += cret ; | |
if(ret >= MOD) ret -= MOD ; | |
} | |
return memo[x][mask] = ret ; | |
} | |
int solve() | |
{ | |
for(int i = 0;i < n;i++) | |
{ | |
block[i] = 0 ; | |
int cmask = 0 ; | |
for(int j = 0;j < m;j++) if(g[i][j] == '#') | |
{ | |
cmask |= 1 << j ; | |
block[i] |= 7 << 3 * j ; | |
} | |
szg[i] = 0 ; | |
for(int j = 0;j < 1 << m;j++) if((j & cmask) == 0) | |
{ | |
bool valid = true ; | |
for(int k = 0;k < m;k++) if(j & 1 << k) | |
for(int kk = k + 1;kk < m && g[i][kk] != '#';kk++) | |
if(j & 1 << kk) | |
valid = false ; | |
if(!valid) continue ; | |
int sp = 0 ; | |
for(int k = 0;k < m;k++) if(j & 1 << k) sp |= 7 << 3 * k ; | |
good[i][szg[i]] = sp ; | |
szg[i]++ ; | |
} | |
} | |
memset(memo,255,sizeof memo) ; | |
memset(memo2,255,sizeof memo2) ; | |
int ret = solve(0,0) ; | |
return ret ; | |
} | |
int main() | |
{ | |
for(int i = 1;i < 1 << 10;i++) bit[i] = bit[i >> 1] + (i & 1) ; | |
int runs ; | |
scanf("%d",&runs) ; | |
while(runs--) | |
{ | |
scanf("%d%d",&n,&m) ; | |
for(int i = 0;i < n;i++) scanf("%s",g[i]) ; | |
int ret = solve() ; | |
ret = (ret - 1 + MOD) % MOD ; | |
printf("%d\n",ret) ; | |
} | |
return 0 ; | |
} |
cool solution. how did you think to it. I would like to know the process that lead you here. I am have a hard time coming up with solutions which get complex. I get that it mainly uses the resusability of solutions. but how did you know there will be so many, along with other things. as much as you can. thanks.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
please explain the spread() function.
Thank you.