ABC361D

問題

ABC361D

解法

連続した空白マス 2つを 1マスとみなすと，順列は高々 $\frac{(N+1)!}{1!\ B!\ W!}$ 通り．
もちろん，ルール上到達出来ない配置も含んでいる．
ここで，$B + W = N$ を満たすので，最大になるのは， $B = W$ のとき．$N = 14$ のとき $51480$．

あとは BFS をすれば良い．遷移は $O(N)$ で行えるので，実行時間に間に合う．

コード

main.cpp

int main() {
  ll n;
  cin >> n;
  string s; cin >> s;
  string t; cin >> t;
  rep(i,2) s.push_back('.'), t.push_back('.');

  map<string, ll> dis;
  queue<string> que; 
  auto push = [&](ll d, string str) -> void {
    if(dis.find(str) == dis.end()){
      dis[str] = d;
      que.push(str);
    }
  };


  push(0, s);
  while(que.size()){
    auto cv = que.front(); que.pop();
    ll cd = dis[cv];

    ll hole = -1; // index
    rep(i,n+1){
      if(cv[i] == '.' && cv[i+1] == '.') {
        hole = i;
        break;
      }
    }

    // swap
    rep(i,n+1) if(cv[i] != '.' && cv[i+1] != '.'){
      swap(cv[i], cv[hole]); swap(cv[i+1], cv[hole+1]);
      push(cd+1, cv);
      swap(cv[i], cv[hole]); swap(cv[i+1], cv[hole+1]);
    }
  }
  cout << (dis.find(t) == dis.end() ? -1: dis[t]) << endl;


  return 0;
}