玛雅人的密码-BFS

题目描述

玛雅人有一种密码，如果字符串中出现连续的2012四个数字就能解开密码。给一个长度为N的字符串，（2=

输入描述:

输入包含多组测试数据，每组测试数据由两行组成。
第一行为一个整数N，代表字符串的长度（2<=N<=13）。
第二行为一个仅由0、1、2组成的，长度为N的字符串。

输出描述:

对于每组测试数据，若可以解出密码，输出最少的移位次数；否则输出-1。

示例1
输入

5
02120

输出

1

解题思路

1、这是一道经典BFS问题，首先判断该字符串有没有“2012”，如果有则返回，没有则循环n-1次，每次移动第i位，加入队列，接下去再在这个基础上继续移动一位，直至找到解。
2、如何判断该字符串已经被访问过？ 可以使用map 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;elsecontinue;}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
#include 
#include
#include
#include
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

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