计算机考研复试之KY12 玛雅人的密码（c++）

描述

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

输入描述：

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

输出描述：

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

输入：
5
02120

输出：
1

思路分析

将不同的字符串视为不同的状态，即运用bfs，宽度优先算法进行遍历搜索即可。

正式总结一下书上提供的BFS思路：

1. 状态。需要确定所求解问题中的状态。通过状态的扩展，遍历所有的状态，从中寻找需要的答案。
2. 状态扩展方式。在宽度优先搜索中，需要尽可能地扩展状态，并对先扩展得到的状态先进行下一次状态扩展
3. 有效状态。对有些状态，并不需要再次扩展它，而是直接舍弃它。因为根据问题的分析可知，目标状态不可能由这些状态经过若干次扩展得到，所以直接舍弃。
4. 队列。为了使得先得出的状态能够先扩展，于是使用队列，将得到的状态依次放入队尾，每次取队头元素进行扩展。
5. 标记。为了判断哪些状态是有效的，哪些是无效的,往往使用标记。
6. 有效状态数。问题中的有效状态数与算法的时间复杂度同数量级，所以在进行搜索之前，必须估算其是否在能够接受的范围内。
7. 最优。宽度优先搜索常被用来求解最优值问题，因为其搜索到的状态总是按照某个关键字递增，这个特性非常适合求解最优值问题。因此，一旦问题中出现最少、最短、最优等关键字，就要考虑是否是宽度优先搜索问题。

代码解析

#include
#include
#include
using namespace std;
struct Node {int num;string str;Node(int n, string s) :num(n), str(s) {}
};
map<string, int> mp;
int bfs(int n, string str) {int count = 0;queue<Node> state;state.push(Node(0, str));while (!state.empty()) {string temp = "";Node cur = state.front();state.pop();//查找mp[cur.str] = 1;for (int i = 0; i < cur.str.size() - 1; ++i) {if (cur.str.find("2012") != string::npos)return cur.num;//交换temp = cur.str;char t = temp.at(i + 1);temp.at(i + 1) = temp.at(i);temp.at(i) = t;//不存在时if (mp.find(temp) == mp.end())state.push(Node(cur.num + 1, temp));}}return -1;
}
int main()
{int n;string str;while (cin >> n && n) {cin >> str;int ans = bfs(n, str);cout << ans << endl;}
}

运行结果

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