Queens on a Board Solution (InterviewStreet CodeSprint Fall 2011)
-
-
Save aishraj/1361928 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 ; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment