AtCoder ABC 361 D - Go Stone Puzzle (1Q, 水色, 425 点)

よくある、パズルの最小手数を求める問題！　この手の問題では、まず「あり得る状態」がどれだけあるかを見積もろう！

• 問題へのリンク

問題概要

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

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

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

具体例

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

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

制約

• 

考えたこと

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

今回は、

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

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

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

コード

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