問題概要

$N+2$ マスがあって、最初、前から $N$ マスには白石か黒石のいずれかが置かれている。置かれ方は文字列 $S$ で表される。後ろ 2 マスは空きマスである。

次の操作を繰り返すことで、前から $N$ マスの置かれ方が文字列 $T$ で表され、後ろ 2 マスは空きマスである状態にしたい。

【操作】
石が置かれているような連続する 2 マスを選び、それらを順序を保ったまま、空きマス (連続 2 マスあることが保証される) へと移動させる。

具体例

$S$ = "BWBWBW"、 $T$ = "WWWBBB" のとき、次のように最短 4 手の操作で実現できる。

BWBWBW..
BW..BWBW
BWWBB..W
..WBBBWW
WWWBBB..

制約

$2 \le N \le 14$

考えたこと

このようなパズルを解く最小手数を求める問題では、BFS を疑う。その際に重要なことは、ありうる状態がどれだけあるかだ。その状態数が十分小さければ、BFS で解くことができる。

今回は、

空きマスの位置としてありうる場合の数： $N + 1$ 通り
石が置かれているマスについての、各マスの石の色の組み合わせ：最大でも $2^{N}$ 通り

ということで、最悪でも $O(2^{N}N)$ 通りであることがわかる。 $N \le 14$ という制約を考えれば、十分にすべて調べ上げることが可能だ (公式解説ではもっと突き詰めている)。

よって、BFS しよう。実装が少し大変。最後に計算量を見積もる。各状態に対して、そこから取れる操作が $O(N)$ 通りあるので、BFS の計算量は $O(2^{N}N^{2})$ と見積もれる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    string S, T;
    cin >> N >> S >> T;
    
    S += "..";
    T += "..";
    map<string, int> dp;
    dp[S] = 0;
    queue<string> que;
    que.push(S);
    while (!que.empty()) {
        auto str = que.front();
        que.pop();
        
        int emp = 0;
        for (int i = 0; i < str.size(); ++i) {
            if (str[i] == '.') {
                emp = i;
                break;
            }
        }
        
        for (int i = 0; i+1 < str.size(); ++i) {
            if (str[i] == '.' || str[i+1] == '.') continue;
            string str2 = str;
            swap(str2[i], str2[emp]);
            swap(str2[i+1], str2[emp+1]);
            if (!dp.count(str2)) {
                dp[str2] = dp[str] + 1;
                que.push(str2);
            }
        }
    }
    if (dp.count(T)) cout << dp[T] << endl;
    else cout << -1 << endl;
}