玛雅人的密码-BFS
程序员文章站
2022-05-21 08:18:23
...
题目描述
玛雅人有一种密码,如果字符串中出现连续的2012四个数字就能解开密码。给一个长度为N的字符串,(2=<N<=13)该字符串中只含有0,1,2三种数字,问这个字符串要移位几次才能解开密码,每次只能移动相邻的两个数字。例如02120经过一次移位,可以得到20120,01220,02210,02102,其中20120符合要求,因此输出为1.如果无论移位多少次都解不开密码,输出-1。
输入描述:
输入包含多组测试数据,每组测试数据由两行组成。
第一行为一个整数N,代表字符串的长度(2<=N<=13)。
第二行为一个仅由0、1、2组成的,长度为N的字符串。
输出描述:
对于每组测试数据,若可以解出密码,输出最少的移位次数;否则输出-1。
示例1
输入
5
02120
输出
1
解题思路
1、这是一道经典BFS问题,首先判断该字符串有没有“2012”,如果有则返回,没有则循环n-1次,每次移动第i位,加入队列,接下去再在这个基础上继续移动一位,直至找到解。
2、如何判断该字符串已经被访问过? 可以使用map<string,int> mp;每次得到一个新的字符串加入map,赋值为1,(初值默认为0),只需要判断mp中字符串对应的int类型即可。
3、创立一个查找函数
查找函数
bool Find(string str)
{
for(int i=0;i<str.size()-3;i++)
{
if(str[i]=='2'&&str[i+1]=='0'&&str[i+2]=='1'&&str[i+3]=='2')
return true;
else
continue;
}
return false;
}
定义一个结构体,记录字符串以及移动字符的次数
struct node{
string str;
int t;
node(string s,int t):str(s),t(t){
}
};
BFS代码
int bfs(string str)
{
map<string,int> mp;
queue<node> myQueue;
myQueue.push(node(str,0));
mp[str]=1;
while(!myQueue.empty())
{
node current=myQueue.front();
myQueue.pop();
if(Find(current.str)) //如果找到了,返回对应的次数
return current.t;
for(int i=0;i<current.str.size()-1;i++) //没找到则交换字符。从第1位一直交换到第n-1位
{
string S=current.str;
swap(S[i],S[i+1]); //交换
if(mp[S]) continue; //如果该字符串已经被访问过,则跳过
mp[S]=1; //没有就记录
myQueue.push(node(S,current.t+1)); //入队列,次数加1
}
}
return -1;
}
主函数
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<string>
using namespace std;
int main()
{
int N;
string str;
while(cin>>N)
{
cin>>str;
cout<<bfs(str)<<endl;
}
return 0;
}
题目链接:https://www.nowcoder.com/questionTerminal/761fc1e2f03742c2aa929c19ba96dbb0
上一篇: 6.30 使用枚举类代替常量
下一篇: android 代替枚举