思路
将原始字符串看作树的根节点,进行一次交换的字符串作为子节点,依次往下交换,然后使用广度优先搜索(BFS)遍历这棵树,也就是层序遍历,每层的字符串对应一个 Map 值,含有2012的字符串在哪一层,就输出该层的 Map 值,如图所示。保证树上的每个结点都不相同,直到穷尽。
#include<iostream> #include<queue> #include<string> #include<unordered_map> using namespace std; struct NewStr{ string s; int step; NewStr(int i, string s):step(i), s(s){} }; unordered_map<string, bool> isVisited;//避免重复入队相同字符串 void bfs(string s){ queue<NewStr> q; q.push(NewStr(0, s)); isVisited[s] = true; while(!q.empty()){ NewStr t = q.front(); q.pop(); string ts = t.s; if(ts.find("2012") != string::npos){ cout << t.step << endl; return; } for(int i = 0; i < ts.size() - 1; i ++){ swap(ts[i], ts[i + 1]); if(!isVisited[ts]) { q.push(NewStr(t.step + 1, ts)); isVisited[ts] = true; } swap(ts[i], ts[i + 1]); } } cout << -1 << endl; } int main(){ int n; string s; while(cin>>n>>s){ bfs(s); } return 0; }