AOJ 2040 : Sort the Panels

問題リンク：Sort the Panels | Aizu Online Judge

問題概要：
長さの同じ文字列が２つA、Bが与えられる
それぞれの文字列は'B'または'W'のみを要素としてもつ
文字列上のどこかにポインタが存在し、自分はそのポインタを１つ左か１つ右かに動かすことができる
この際にコストが１かかる
また、ポインタのある場所にマークをつけることができる
マークは異なる2ヶ所につけることができて、2ヶ所つけた後その２つのマークのつけられた場所にある文字をスワップする
スワップ後マークは消える
文字列Aから文字列Bにするまでに必要なコストの最小値を求めたい
ポインタの初期位置は自由に決めて良い

解法：
ビットDP
文字列Aの各要素を文字列Bの正しい位置に配置していく
既に正しい位置に配置したかどうかの状態をビットとしてもっておく
dp[今ポインタがある場所][正しい場所に移動させた文字の状態] := 最小コスト
各場所についてスワップは2度以上行われない

コード：

#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 LIMIT = (1<<16), IINF = INT_MAX;

bool fin[LIMIT];
int N,dp[16][LIMIT];
string a,b;

int main(){
  while( cin >> N, N ){
    cin.ignore();
    getline(cin,a);
    getline(cin,b);

    if( a == b ) {
      puts("0");
      continue;
    }

    rep(i,N)rep(j,(1<<N)) dp[i][j] = IINF;
    rep(i,N) dp[i][0] = 0;

    rep(i,(1<<N)) {
      fin[i] = true;
      rep(j,N){
        if((i>>j) & 1) continue;
        if( a[j] != b[j] ) {
          fin[i] = false;
          break;
        }
      }
    }

    rep(state,(1<<N)){
      rep(cur,N){
        if( dp[cur][state] == IINF ) continue;
        rep(from,N){
          if( (state>>from) & 1 ) continue;
          rep(to,N){
            if( from == to ) continue;
            if( (state>>to) & 1 ) continue;
            if( !( a[from] == b[to] && a[to] == b[from] ) ) continue;
            int nstate = state|(1<<from)|(1<<to);
            if( fin[nstate] ) nstate = (1<<N)-1;
            dp[to][nstate] = min(dp[to][nstate],
                                 dp[cur][state] + abs(cur-from) + abs(from-to));
          }
        }
      }
    }

    int mini = IINF;
    rep(i,N) mini = min(mini,dp[i][(1<<N)-1]);
    cout << mini << endl;
  }
  return 0;
}