首页 > 其他 > 详细

密码锁

时间:2020-04-18 11:01:56      阅读:34      评论:0      收藏:0      [点我收藏+]

玛雅人的密码(清华大学)牛客复试题

题目链接:https://www.nowcoder.com/practice/7da5fb77ba2e462c909fbff8f61584be?tpId=40&tqId=30987&tPage=2&rp=2&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking

思路:每个密码一次相邻位置的交换只能出现n个位置。利用BFS和DFS都可以搜索所有交换组合,但是要求最小的交换次数,应该用BFS。利用map记录已经出现过的组合,防止死循环。遍历所有交换组合,寻找存在2012substr的最小交换次数。

code:

#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;
int main()
{
	int n;
	while (cin>>n)
	{
		string line;
		cin >> line;
		bool flag = false;
		map<string, int > mp;
		queue<string> q;
		q.push(line);
		mp[line] = 0;
		while (!q.empty()) {
			string p = q.front();//队头
			q.pop();

			if (p.find("2012") != string::npos) {//存在2012
				cout << mp[p] << endl;
				flag = true;
				break;
			}
			
			for (int i = 0; i < p.size()-1; i++)//将p交换状态下再交换的所有未出现过额状态入队
			{
				string temp = p;
				swap(temp[i], temp[i + 1]);
				if (mp.find(temp) == mp.end()) {
					mp[temp] = mp[p] + 1;//记录temp已经进过队
					q.push(temp);//入队
				}
			}
		}
		if (!flag) {
			cout << -1 << endl;
		}
	}
}

密码锁

原文:https://www.cnblogs.com/custoyth/p/12724200.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!