广度优先搜索,用了unordered_map标记字符串是否已经被访问过
#include <iostream> #include <queue> #include "queue" #include "unordered_map" using namespace std; struct status { string code; int count; status(string s, int a) { code = s; count = a; } }; int bfs(string code){ queue<status> countQueue; unordered_map<string,bool> visitMap; countQueue.push(status(code, 0)); visitMap[code]=true; while (!countQueue.empty()) { status current = countQueue.front(); countQueue.pop(); if (current.code.find("2012") != string::npos) { return current.count; } for(int i=0;i<=code.size()-2;i++){ string temp=current.code; swap(temp[i],temp[i+1]); if(visitMap[temp]) continue; countQueue.push(status(temp,current.count+1)); visitMap[temp]=true; } } return -1; } int main() { int n; string code; while (cin >> n >> code) { // 注意 while 处理多个 case cout << bfs(code)<< endl; } } // 64 位输出请用 printf("%lld")