蓝桥杯 ADV-161 算法提高 题目 2 密码锁
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了蓝桥杯 ADV-161 算法提高 题目 2 密码锁，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1775字，纯文字阅读大概需要3分钟。
内容图文
算法提高 题目 2 密码锁
时间限制：1.0s 内存限制：1.0GB
问题描述
你获得了一个据说是古代玛雅人制作的箱子。你非常想打开箱子看看里面有什么东西,但是不幸的是,正如所有故事里一样,神秘的箱子出现的时候总是会挂着神秘的锁。
这个锁上面看起来有 N 个数字,它们排成一排,并且每个数字都在 0 到 2 之间。你发现你可以通过锁上的机关来交换相邻两个数字的顺序。比如,如果原来有 5 个数字 02120,在一次交换以后你就可以得到 20120,01220,02210 或者 02102。
根据你所搜集的情报,这个锁在上面存在某连续四个数字是“2012”的时候会自动打开。现在,你需要计算一下,你至少需要进行多少次交换操作才能打开这把锁?
输入格式
输入数据的第一行有一个正整数 N。(4 ≤ N ≤ 13) 输入数据的第二行有 N 个数字 a1,a2, …, aN ,其中 ai 表示这个锁上面第 i 个数字的值,满足 0 ≤ ai ≤ 2。这些数字之间没有空格分隔。
输出格式
你只需要输出一个数字,即你至少需要的交换次数。如果无论如何都没有希望打开这把锁,输出 -1。
样例输入
5
02120
样例输出
1
对样例的解释
把前两个数字交换以后,锁上的数字是 20120,其中存在连续四个数字2, 0, 1, 2,因此锁会打开。
#include <iostream>
#include <set>
#include <queue>
using namespace std;
int num_swap;
set<string> states;
queue<string> pool;
int unLock()
{
string Lock;
while (pool.size() > 0)
{
queue<string> next_states;
num_swap++;
while (pool.size() > 0)
{
Lock = pool.front();
pool.pop();
if (Lock.find("2012") != string::npos)
return 1;
for (int i = 0; i <= Lock.length() - 2; ++i)
{
swap(Lock[i], Lock[i+1]);
if (states.find(Lock) == states.end())
{
states.insert(Lock);
next_states.push(Lock);
}
swap(Lock[i], Lock[i+1]);
}
}
pool = next_states;
next_states.empty();
}
return 0;
}
int main()
{
int N;
string Lock;
cin >> N;
cin >> Lock;
num_swap = -1;
states.insert(Lock);
pool.push(Lock);
if (unLock())
printf("%d", num_swap);
else
printf("-1");
return 0;
}
liulizhi1996 发布了317 篇原创文章 · 获赞 44 · 访问量 4万+ 私信 关注
内容总结
以上是互联网集市为您收集整理的蓝桥杯 ADV-161 算法提高 题目 2 密码锁全部内容，希望文章能够帮你解决蓝桥杯 ADV-161 算法提高 题目 2 密码锁所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。