Queens on a Board Solution (InterviewStreet CodeSprint Fall 2011)

Hint.md

Queens on a Board Solution (InterviewStreet CodeSprint Fall 2011)

problemsetter.cpp

#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 ;
}