判断是否有解

对字符串的操作完全类似于冒泡排序。只要字符串中存在两个‘2’，一个‘1’和一个‘0’，则一定可以得到“2012”。故可提前判断一下是否存在这几个字符，如不满足，可提前输出-1，不用进行大量的搜索查找。
该优化可以将运行时间从60ms降到20ms左右。

为什么不加判断也是可以的？
由于这里的字符串比较短（最长13），字符集又只有‘012’，所以没多少种情况，全部搜索完后发现都不存在“2012”的字串，也可得出无解结论。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <unordered_map>

using namespace std;

int n;
string s;
unordered_map<string, int> step;

int bfs()
{
    queue<string> q;
    q.push(s);
    step[s] = 1;

    while (q.size())
    {
        string cur = q.front();
        q.pop();

        if (cur.find("2012") != string::npos) return step[cur] - 1;

        for (int i = 1; i < cur.size(); i ++ )
        {
            string old = cur;
            swap(cur[i], cur[i - 1]);
            if (step[cur] == 0)
            {
                q.push(cur);
                step[cur] = step[old] + 1;
            }

            swap(cur[i], cur[i - 1]);
        }
    }

    return -1;
}


int main()
{
    cin >> n >> s;

    int r1 = 0, r0 = 0, r2 = 0;
    for (auto c : s)
        if (c == '0') r0 ++ ;
        else if (c == '1') r1 ++ ;
        else if (c == '2') r2 ++ ;


    if (r0 < 1 || r1 < 1 || r2 < 2)   // 这种情况无解
        cout << -1 << endl;         
    else                              // 反之一定有解
        cout << bfs() << endl;

    return 0;
}