首页 > 试题广场 >

玛雅人的密码

[编程题]玛雅人的密码
  • 热度指数：24339 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
玛雅人有一种密码，如果字符串中出现连续的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
算法知识视频讲解
开通博客
头像 philos
发表于 2021-02-04 11:38:47
思路 将原始字符串看作树的根节点，进行一次交换的字符串作为子节点，依次往下交换，然后使用广度优先搜索（BFS）遍历这棵树，也就是层序遍历，每层的字符串对应一个 Map 值，含有2012的字符串在哪一层，就输出该层的 Map 值，如图所示。保证树上的每个结点都不相同，直到穷尽。 #include& 展开全文
去ta的博客 赞 (28) 回复(0) 收起
头像 健康快乐最重要
发表于 2020-03-26 11:42:14
没有任何优化的无脑暴力bfs #include<iostream> #include<queue> #include<string> using namespace std; struct mitery{ int index; string s; 展开全文
去ta的博客 赞 (19) 回复(4) 收起
头像 sNowEmber
发表于 2022-03-14 00:03:25
简单易懂bfs，宝宝也能学会~ #include<bits/stdc++.h> using namespace std; struct str{ int count; //记录移动次数（为什么要加？答：因为bfs队列一直在循环，不清楚排队的兄弟经过了几次字符移动） st 展开全文
去ta的博客 赞 (8) 回复(0) 收起
头像 谁的衣服没晒
发表于 2022-02-19 12:53:11
萌新利用BFS的暴力解法，相对来说应该比较好理解！ 主要技巧是构造一个结构体，记录字符串以及得到这个字符串所用的交换次数。 我觉得本题的关键在于记录交换次数增加的时候位置要选择在正确的循环内，就像我在41行注释掉的那样。然而话说回来，在用int cnt（41行）而非mark对象的cnt（ 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 七灵微
发表于 2024-08-02 17:57:24
import sys def swap(s,i,j): #print(i,j) if(j+1<len(s)): s=s[:i]+s[j]+s[i]+s[j+1:] elif(j+1==len(s)):s=s[:i]+s[j] else:s=s[: 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 牛客600247800号
发表于 2022-02-19 23:09:58
#include <iostream> #include <string> #include <vector> #include <queue> #include <set> using namespace std; set<str 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 Youlinw
发表于 2024-02-23 01:17:58
#include <bits/stdc++.h> using namespace std; const int N = 20; int n; string start; bool check(string s) { int len = s.length(); for (int i 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 西区梭梭树
发表于 2023-03-12 18:18:20
广度优先搜索，通过搜索状态结构体记录每一层的移动次数 #include <iostream> #include <queue> #include <unordered_map> using namespace std; struct status { st 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 程昱同学
发表于 2023-01-19 10:35:38
#include <iostream> #include <map> #include <queue> using namespace std; map<string, bool> visited; queue<pair<string, i 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 牛客440904392号
发表于 2024-10-05 10:58:46
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); Label: 展开全文
去ta的博客 赞 (1) 回复(0) 收起

问题信息

搜索 图
难度：
130条回答 18586浏览

热门推荐

通过挑战的用户

查看代码

相关试题

玛雅人的密码

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号