UVa 10651 : Pebble Solitaire

UVa演習 2014/6/10 (火) 問1

問題リンク : http://uva.onlinejudge.org/external/106/10651.html

問題概要 :
12個の穴が一列に空いている
穴には小石がつまっている場合がある
隣接する３つの穴のうち、隣接する２つに小石がつまっている場合２つの小石を消去し、何もつまっていない穴に小石をつめることができる
初期状態が与えられるので、小石の数を最小化せよ

解法:
メモ化再帰する

コード：

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

const int IINF = INT_MAX;
int memo[1<<12];

int dfs(int bitmask){
  if( memo[bitmask] != IINF ) return memo[bitmask];
  int &ret = memo[bitmask];
  bool update = false;
  rep(i,12){
    if( ((bitmask>>i)&1) ) continue;
    if( (i-1>=0) && (i-2>=0) && ((bitmask>>(i-1))&1) && ((bitmask>>(i-2))&1) ){
      int nbitmask = bitmask & ~(1<<(i-1));
      nbitmask &= ~(1<<(i-2));
      nbitmask |= (1<<i);
      ret = min(ret,dfs(nbitmask));
      update = true;
    }
    if( (i+1<12) && (i+2<12) && ((bitmask>>(i+1))&1) && ((bitmask>>(i+2))&1) ){
      int nbitmask = bitmask & ~(1<<(i+1));
      nbitmask &= ~(1<<(i+2));
      nbitmask |= (1<<i);
      ret = min(ret,dfs(nbitmask));
      update = true;
    }
  }
  if( !update ) ret = __builtin_popcount(bitmask);
  return ret;
}

int main(){
  rep(i,(1<<12)) memo[i] = IINF;
  memo[0] = 0;
  string line;
  int T;
  cin >> T;
  while( T-- ) {
    cin >> line;
    int bitmask = 0;
    rep(i,12) if( line[i] == 'o' ) bitmask |= (1<<i);
    cout << dfs(bitmask) << endl;
  }
  return 0;
}