题解 | 玛雅人的密码

#include <iostream>
#include<map>
#include<queue>
//这题应该时用bfs因为要在转换后的数字上接着交换
using namespace std;
map<string, int>find_str;
int pos[2] = { -1,1 };
bool judge(string str) {
    for (int i = 0; i <= str.size() - 4; i++) {
        string tmp = str.substr(i, 4);
        if (tmp == "2012")return true;
    }
        
    return false;
}
// 将数组用于函数传递，函数内对数组的改变也会影响调用函数外的该数组
//但是string作为参数传递，并不会影响外部除非采用引用传递
void bfs(string str) {
    queue<string>q;
    q.push(str);
    find_str[str] = 0;
    if (judge(str)) {
        cout << 0;
        return;
    }
    while (!q.empty()) {
        
        string tmp = q.front();
        q.pop();
        //注意本题只能移动相邻的数字
        for (int i = 0; i < tmp.size()-1; i++) {
            for (int j = 0; j <2; j++) {
                if (i + pos[j] >= 0&&i+pos[j]<tmp.size()) {
                    string mid = tmp;
                    swap(mid[i], mid[i + pos[j]]);
                    if (find_str.count(mid) == 0) {
                        find_str[mid] = find_str[tmp]+1;
                        q.push(mid);
                       /* cout << mid << endl;*/
                        if (judge(mid)) {
                            cout << find_str[mid] << endl;
                            return;
                        }

                    }
                }
            }

            }
        }
    
    cout << -1 << endl;
}
int main() {
    string str;
    int n;
    while (cin >> n >> str) {
        bfs(str);
    }

}
// 64 位输出请用 printf("%lld")