1. 原题描述

玛雅人有一种密码，如果字符串中出现连续的 2012 四个数字就能解开密码。给一个长度为N的字符串，（2=<N<=13）该字符串中只含有 0, 1, 2 三种数字，问这个字符串要移位几次才能解开密码，每次只能移动相邻的两个数字。例如 02120 经过一次移位，可以得到 20120, 01220, 02210, 02102，其中 20120 符合要求，因此输出为 1。如果无论移位多少次都解不开密码，输出 -1。

输入包含多组测试数据，每组测试数据由两行组成。第一行为一个整数N，代表字符串的长度（2<=N<=13）。第二行为一个仅由0、1、2组成的，长度为N的字符串。

对于每组测试数据，若可以解出密码，输出最少的移位次数；否则输出-1。

2. 分析与踩坑

很明显这就是一个搜索的题目，之所以要记录这道题是因为我踩了两个坑:

错误地用了 DFS
BFS 的搜索方向错了

2.1 踩坑一：用了 DFS

由于以前天天用 DFS，结果本能的用了深度优先搜索:

void Switch(int i)
{
    char ch = pwd[i];
    pwd[i] = pwd[i - 1];
    pwd[i - 1] = ch;
}
void Dfs(int cur)
{
    if (Ok())
    {
        //cout << step << ": " << pwd << endl;
        minStep = (step < minStep)? step : minStep;
        return;
    }
    for (int i = cur; i < pwd.length(); ++i)
    {
        //不交换
        Dfs(cur + 1);
        //交换
        Switch(i);
        step++;
        Dfs(cur + 1);
        Switch(i);
        step--;
    }
}

这个代码到底能不能 AC 我不知道，反正超时了，后来我才想起来，求取类似于最小值的时候，应该使用 BFS 而非 DFS。

2.2 踩坑二：BFS 的搜索方向搞错了

我一开始的 BFS 的代码是直接根据 DFS 改过来的:

struct Tuple
{
    string s;
    //上一次访问到哪一位了
    int cursor;
    //交换过几次
    int step = 0;
    //不要用引用 &
    Tuple(string s, int c, int step)
    {
        this->s = s;
        this->cursor = c;
        this->step = step;
    }
};

int Bfs(string &pwd)
{
    queue<Tuple> q;
    //初始结点压入队列
    Tuple initNode(pwd, 1, 0);
    q.push(initNode);
    Tuple *ptr;
    int minStep = 2e9;
    while (!q.empty())
    {
        //访问结点
        ptr = &q.front();
        q.pop();
        string &s = ptr->s;
        int cur = ptr->cursor;
        int step = ptr->step;
        //看是不是符合要求的
        if (Ok(s))
        {
            //cout << s << " " << cur << " " << step << endl;
            if (step < minStep)
                minStep = step;
        }
        if (cur < pwd.length())
        {
            //往子树方向搜索
            //不移动
            Tuple t1(s, cur + 1, step);
            q.push(t1);
            //移动
            Switch(s, cur);
            Tuple t2(s, cur + 1, step + 1);
            q.push(t2);
        }
    }
    if (minStep == 2e9)
        return -1;
    else
        return minStep;
}

表面上看似乎没问题，然而求解的答案却是错误的。后来我仔细分析，才发现是我把搜索的方向弄错了。

这一点我以前一直没有注意过，而这次才意识到还存在这么一个问题。啥意思呢？我们知道无论是 DFS 还是 BFS 其实都是把解空间建模成一颗树来进行搜索。所以搜索到的结果的顺序就和怎么建立这棵树密切相关。

来看看在之前的代码中我们的树是怎么建立的，比如我现在输入的密码是 02120，那么搜索的树的结构是这样的:

graph TD
Start-->A(02120);
Start-->B(20120);
A-->c(02120);
A-->d(01220);
B-->e(20120);
B-->f(21020);

之前两份代码，无论是 DFS 还是 BFS 都是在这么一棵树上搜索。这棵树从上到下的层次是按照移动的位置排列的。即从前往后一次遍历密码，然后分别按照是否移动当前位来分裂出不同子树。所以在这棵树上进行 BFS ，搜索出来的结果并非是“移动次数最小”，而是“最靠前”。

那么如果我们希望找到“移动次数最小”，那应该构建这么一棵树:

graph TD
Start(02120) --> b(20120);
Start --> c(01220);
Start --> d(02210);
Start --> e(02102);

根据这棵树，我们可以写出新的 BFS 代码。

3. AC 代码

#include <iostream>
#include <string>
#include <queue>
using namespace std;

bool Ok(string &s)
{
    size_t x = s.find("2012");
    return x != string::npos;
}

struct Pair
{
    string s;
    //交换过几次
    int step = 0;
    Pair(string s, int step): s(s), step(step) {}
};

string Switch(string str, int i)
{
    char ch = str[i];
    str[i] = str[i - 1];
    str[i - 1] = ch;
    return str;
}

int Bfs(string &pwd)
{
    if (Ok(pwd))
        return 0;
    queue<Pair> q;
    //初始结点压入队列
    Pair initNode(pwd, 0);
    q.push(initNode);
    Pair *ptr;
    while (!q.empty())
    {
        //访问结点
        ptr = &q.front();
        q.pop();
        string &s = ptr->s;
        int step = ptr->step;
        //进行一次交换，注意是朝着 step 增大的方向搜索的
        for (int i = 1; i < s.length(); ++i)
        {
            string newStr = Switch(s, i);
            //如果可以的话，那么这个 step 必然是最小的
            if (Ok(newStr))
                return step + 1;
            else
            {
                Pair node(newStr, step + 1);
                q.push(node);
            }
        }
    }
    return -1;
}

int main()
{
    string pwd;
    int N;
    while (cin >> N >> pwd)
    {
        if (N < 4)
        {
            cout << -1 << endl;
            continue;
        }
        cout << Bfs(pwd) << endl;
    }
    return 0;
}