【AtCoder】ABC 361 D - Go Stone Puzzle | 茶コーダーが解くAtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 1202

問題概要

$N+2$ 個のマスが横一列に並んでおり、左から $i$ 個目のマスをマス $i$ とする。マス $1$ からマス $N$ には白か黒の石が置かれており、マス $N+1, N+2$ は何も置かれていない。なお、 $N$ 個のマスの状況は文字列 $S$ で表され、 $S_i \: (1 \leq i \leq N)$ がWのときは白の石、Bのときは黒の石が置かれていることを示す。

このとき、「石が2個並んでいる箇所を選び、その2個の石を順序を保って空きマスに移す」という操作を0回以上行って以下の状態にすることが可能か判定し、可能なら操作回数の最小値を求めよ。不可能ならば-1を出力せよ。

マス $1$ からマス $N$ まで石が置かれ、文字列 $T$ について $T_i$ がWのときは白の石、Bのときは黒の石が置かれていることを示す。

制約

$N$ は整数で $2 \leq N \leq 14$ を満たす。
$S, T$ はB, Wからなる長さ $N$ の文字列。

考察

「ある盤面から目標の盤面を達成するために必要な最小手数を求める」ようなの問題 (状態空間問題) では、スタートとなる盤面から実現可能な盤面を全て列挙し、その中に目標の盤面が存在するかをチェックするという方針が有効なことが多い。今回の問題もそれが適用できるかを確かめてみる。

$N+2$ 個のマスに $b$ 個のBと $w$ 個のWと2個の.を1つずつ置いていく場合の数は、.を必ず隣同士に配置することに注意すると、重複組合せの要領で $\dfrac{(N+1)!}{b!w!} \quad (2 \leq N \leq 14, \, 0 \leq b + w \leq N, \, b > 0, \, w > 0)$ と計算できる。これが最大になるのは $N = 14, \, b = w = 7$ のときで、 $\dfrac{(N+1)!}{b!w!} = 51480$ であり、これは全列挙するのに十分小さい。また、ある状態から次の状態への遷移の候補も高々 $N - 1$ 通りしかないので、この問題も上述の方針が適用できそうだ。

この方針は、幅優先探索 (BFS) を用いることで実現できる。これは下図を見てもらうと分かりやすいだろう。

これは $N = 4$ , $S =$ BWBW, $T =$ WBWBの場合について、実現可能な状態を木構造で表したものである。ただし、ある頂点と同じ状態が自身よりも上、または左の頂点に存在する場合はその時点で遷移を打ち切ることにしている。

各状態を実現するための最小手数はその頂点の深さに対応しているので、 BFS を用いて全ての状態を列挙していくことにより、処理の効率化を図ることができる。

実装においては、連想配列に今の石の状況をキー、操作回数を値として格納してやることがポイント。 $S, T$ の末尾に..を付加しておくことを忘れないようにすること (自戒) 。

コード

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

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

// ======================================== //

int main()
{
    int N;
    cin >> N;
    string S, T;
    cin >> S >> T;

    S += "..";
    T += "..";

    map<string, int> states;
    states[S] = 0;

    queue<string> que;
    que.push(S);

    while (!que.empty())
    {
        string now = que.front();
        que.pop();

        if (now == T)
        {
            cout << states[now] << endl;
            return 0;
        }

        rep(i, 0, N + 1)
        {
            string stones = now.substr(i, 2);

            if (stones[0] != '.' && stones[1] != '.')
            {
                rep(j, 0, N + 1)
                {
                    if (now[j] == '.' && now[j + 1] == '.')
                    {
                        string next = now;
                        next[i] = '.';
                        next[i + 1] = '.';
                        next[j] = stones[0];
                        next[j + 1] = stones[1];

                        if (states.find(next) == states.end())
                        {
                            states[next] = states[now] + 1;
                            que.push(next);
                        }
                    }
                }
            }
        }
    }

    cout << -1 << endl;
    return 0;
}