【牛客网】KY12 玛雅人的密码

这是一道BFS的题目，因为要找到通过移位可以得到的2012，并输出移位的次数，因此可以用BFS的思想进行遍历：

#include
#include
#include
#includeusing namespace std;struct Statue{string s;int times;Statue(string s, int t): s(s), times(t){}
};int BFS(string str){queue<Statue> q;map<string, int> m;m[str] = 1;q.push(Statue(str, 0));while(!q.empty()){Statue current = q.front();q.pop();if(current.s.find("2012", 0) != -1) return current.times;int n = current.s.size();for(int i = 0;i < n - 1;i++){Statue temp = current;char ch = temp.s[i];temp.s[i] = temp.s[i + 1];temp.s[i + 1] = ch;if(m[temp.s]) continue;  //已经访问过了m[temp.s] = 1;temp.times++;q.push(temp);}}return -1;
}int main(){int n;string str;while(cin>>n>>str){printf("%d\n", BFS(str));}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！