首页 > 试题广场 >

玛雅人的密码

[编程题]玛雅人的密码
  • 热度指数:22360 时间限制: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
bfs就行,要注意不用移位就有2012子串的情况。
#include <stdio.h>
#include <queue>
#include <string>
#include <iostream>
using namespace std;

bool pan(string a,int n) {
     bool flag=false;
     for(int i=0; i<n-3; i++) {
        if(a[i]=='2'&&a[i+1]=='0'&&a[i+2]=='1'&&a[i+3]=='2') {
            flag=true;
            break;
        }
    }
    return flag;
}

string swap(string a,int i,int j) {
    char temp=a[i];
    a[i]=a[j];
    a[j]=temp;
    return a;
}

struct E {
    string a;
    int t;
};
queue<E> Q;
int BFS(int n) {
    while(Q.empty()==false) {
        E now=Q.front();
        Q.pop();
        if(pan(now.a,n)){
            return now.t;
        }
        else{
            for(int i=0; i<n-1; i++) {
                string new_a=swap(now.a,i,i+1);
                int new_t=now.t+1;
                if(new_t>20) {
                    return -1;
                } else {
                    if(pan(new_a,n)) {
                        return new_t;
                    } else {
                        E tmp;
                        tmp.a=new_a;
                        tmp.t=new_t;
                        Q.push(tmp);
                    }
                }
            }
        }
    }
    return -1;
}
int main() {
    int n;
    string str;
    while(cin>>n>>str) {
        while(Q.empty()==false){
            Q.pop();
        }
        E tmp;
        tmp.a=str;
        tmp.t=0;
        Q.push(tmp);
        int ans=BFS(n);
        printf("%d\n",ans);
    }
    return 0;
}

发表于 2018-02-16 17:33:15 回复(5)
#include<iostream>
#include<string>
#include<map>
#include<queue>
using namespace std;
int n;
bool judge(string s)
{
	int l=s.size();
	for(int i=0;i<l-3;i++)
	{
		if(s[i]=='2'&&s[i+1]=='0'&&s[i+2]=='1'&&s[i+3]=='2')
		{
			return true;
		}
	}
	return false;
}
int bfs(string s)
{
	map<string,int>mp;//如果遍历过,将second标记为1
	mp.clear();//清空上一次的缓存
	queue<pair<string,int>>que;//用队列来保存搜索的路径
	que.push(make_pair(s,0));//将第一个string入队
	while(!que.empty())//如果遍历过所有string,返回-1
	{
		pair<string,int> now=que.front();
		que.pop();//队头的string出队
		string str=now.first;
		if(judge(str))
			return now.second;
		if(mp[str])//如果该排列已经judge过,则跳到下一个排列
			continue;
		mp[str]=1;//如果没有就标记为已遍历过
		for(int i=0;i<n-1;i++)//创建新的排列
		{
			swap(str[i],str[i+1]);
			que.push(make_pair(str,now.second+1));
			swap(str[i],str[i+1]);
		}
	}
	return  -1;
}
int main()
{
	string s;
	while(cin>>n)
	{
		cin>>s;
		cout<<bfs(s)<<endl;
	}
	return 0;
}
借鉴了评论区的代码,BFS很赞
发表于 2017-07-15 16:06:14 回复(0)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <map>
#include <utility>
using namespace std;
const int N = 1010;
typedef pair<string, int> pii;
int n;
bool judge(string s){
    int len = s.length();
    for(int i = 0; i < len - 3; i++){
        if(s[i] == '2' && s[i + 1] == '0' && s[i + 2] == '1' && s[i + 3] == '2')return true;
    }
    return false;
}
int bfs(string s){
    map<string, int>mp;
    mp.clear();
    queue<pii>que;
    que.push(make_pair(s, 0));
    while(!que.empty()){
        pii now = que.front();
        que.pop();
        string str = now.first;
        if(judge(str))return now.second;
        if(mp[str])continue;
        mp[str] = 1;
        for(int i = 0; i < n - 1; i++){
            swap(str[i], str[i + 1]);
            que.push(make_pair(str, now.second + 1));
            swap(str[i], str[i + 1]);
        }
    }
    return -1;
}
int main(){
    string s;
    while(scanf("%d", &n) > 0){
        cin >> s;
        int f = bfs(s);
        printf("%d\n", f);
    }
}
经典的bfs搜索

发表于 2016-05-01 14:46:44 回复(2)
唉,这些题目做多了,有种电脑再好也怕炸掉的感觉。
该题目的思路就是:
    如何用队列广度优先遍历所有可能性(QUEUE) + 如何判别并标示某串是否访问过(MAP) + 如何记录某串已经交换字符的次数 + 子串2012是否存在
    这几个问题如果解决了我想你肯定能写出来。
    希望同学看了以上内容先不要看下面的程序,自己想办法按着上面的思路再好好写一遍。
#include<iostream>
#include<queue>
#include<map>
#include<string>


using namespace std;

char Aim[] = "2012";

typedef struct str_cos{     string str;                             //包含的字符串     int deep;                                //标示该串做了几次字符交换     str_cos(string str,int deep) {         this->deep = deep;         this->str = str;     }
}STR;

bool SubString(string S){  //判断某个字符串是否包含子串"2012"     int p = 0;     int q = 0;     while(p < S.size()){         if(S[p] == Aim[q]){             q++;         }         else{             q = 0;                     }         p++;         if(q == 4)             return true;     }     return false;
}

int MoveCounter(STR str){     queue<STR> Q;     map<string, int> MAP;          //用来区分该串是否之前已经生成过     char T;     int Length = str.str.size();     string S_temp;     Q.push(str);                   //原始串入队,为接下来的广度遍历做准备     MAP[str.str] = 1;              //标示原始串已经访问过,1是看心情给的     while (!Q.empty()) {         STR F_temp = Q.front();             Q.pop();         if (SubString(F_temp.str))                               //若该串满足题目要求,则输出深度(字符交换次数)             return F_temp.deep;         for (int i = 0; i < str.str.size() - 1; ++i) {           //该循环是用来把当前串的所有可能的相邻交换(一次)列出来             S_temp = F_temp.str;             T = S_temp[i];             S_temp[i] = S_temp[i + 1];             S_temp[i + 1] = T;             if (MAP.find(S_temp) == MAP.end()) {                 //若该交换后的新串先前木有出现过,则标示已访问,并入队。                 MAP[S_temp] = 1;                 Q.push(str_cos(S_temp, F_temp.deep + 1));             }         }     }     return -1;      }

int main(){     string S;     int N;     while(scanf("%d",&N) != EOF){   //这个N你可以看心情给!         cin>>S;         printf("%d\n",MoveCounter(str_cos(S,0)));     }     return 0;
}

发表于 2017-10-02 22:24:06 回复(1)
/*
 * QQ:	825580813
 * 把所有的转换后的字符串都列出来,然后判断这其中是否包含"2012"即可.
 * 
 * 那么如何把他们都列出来呢?
 * 
 * 建立一张图,根据宽度优先遍历即可,(按理说,图有两种遍历,为何偏偏选择宽度优先呢)
 * 因为,这张图的建立过程与遍历过程同时进行.
 * 
 * 建立图的方法:
 * 		将源字符串作为第一个节点, 然后将它的移位字符串作为邻接点即可.
 */
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class StringNum{
	String str;
	int num;
	public StringNum(String str, int num) {
		this.str = str;
		this.num = num;
	}
}

public class MayanCode {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		while (sc.hasNextInt()) {
			int n = sc.nextInt();
			String code = sc.next();
			int moveTime = getMoveTime(code, n);
			System.out.println(moveTime);
		}
		sc.close();
	}

	private static int getMoveTime(String code, int n) {
		if (n < 4) {
			return -1;
		}
		ArrayList<String> record = new ArrayList<>();
		Queue<StringNum> que = new LinkedList<>();
		StringNum stringNum = new StringNum(code, 0);
		que.offer(stringNum);
		record.add(code);
		while (!que.isEmpty()) {
			stringNum = que.remove();
			if (stringNum.str.contains("2012")) {
				return stringNum.num;
			}
			for (int i = 0; i < n - 1; ++i) {
				char[] temp = stringNum.str.toCharArray();
				swap(temp, i, i + 1);
				String tempStr = new String(temp);
				if (!record.contains(tempStr)) {
					record.add(tempStr);
					que.offer(new StringNum(tempStr, stringNum.num + 1));
				}
			}
		}
		return -1;
	}

	private static void swap(char[] arr, int i, int j) {
		char temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
		
	}

}


发表于 2017-05-23 10:37:41 回复(3)
//BFS即可,注意换位后要恢复原样,不然会影响之后的循环
//队列可以不用指针式,直接开成结构体型避免了malloc()申请内存

#include <stdio.h>
#include <string.h>

#define MAXSIZE 200000  //注意自己写队列的时候要开足够大 有个十三位的数据 必须要
                        //用到二十万的队列 不然结果会是错的,通不过的可以看看是不
                        //队列爆了

typedef struct passWord{
    char str[13];
    int n;
    int cost;
}passWord;

int isPW(passWord pw){
    int n=pw.n;
    int i;
    for(i=0;i<n-3;i++){
        if(pw.str[i]=='2'&&pw.str[i+1]=='0'&&pw.str[i+2]=='1'&&pw.str[i+3]=='2') return 1;
    }
    return 0;
}

int BFS(passWord pw){
    passWord queue[MAXSIZE];
    int i;
    int front=0,end=0;
    queue[end]=pw;
    end=(end+1)%MAXSIZE;
    while(front!=end){
        passWord p=queue[front];
        front=(front+1)%MAXSIZE;
        if(isPW(p)){
            return p.cost;
        }else {
            for(i=0;i<p.n-1;i++){
                char temp = p.str[i];
                p.str[i]=p.str[i+1];
                p.str[i+1]=temp;
                p.cost++;
                queue[end]=p;
                end=(end+1)%MAXSIZE;
                temp = p.str[i];
                p.str[i]=p.str[i+1];
                p.str[i+1]=temp;
                p.cost--;

            }
        }
    }
    return -1;
}


int main(){
    passWord pw;
    int n;
    scanf("%d",&n);
    scanf("%s",pw.str);
    pw.n=n;
    pw.cost=0;
    printf("%d\n",BFS(pw));


    return 0;
}

编辑于 2020-02-17 10:46:27 回复(0)
//此题是用递归做的
#include<stdio.h>
#include<string.h>
int min;
int flag[14];//标记
void swap(char *p,char *q)
{
    char temp;
    temp=*p;
    *p=*q;
    *q=temp;
}
void find(char str[],int n,int k)//k值存移动次数,n存字符串大小
{
    int i;
    char t[5]="2012";
    if(strstr(str,t)!=NULL) //这是string库里面的函数,若没有找到子字符串就返回NULL
    {
        if (k<min) min=k;
        return;
    }
    else if(k>min) return;
    for(i=0;i<n-1;i++)//从头开始,挨个交换
        {
            if(flag[i]==0)
            {
            swap(&str[i],&str[i+1]);//交换过后,下次就不再交换,如ab 交换后为ba,若不标记下次就有要交换成ab
            flag[i]=1;//将该位置标记
            find(str,n,k+1);//此次交换过后,k++,进行下一轮判定
            swap(&str[i],&str[i+1]);//返回原状
            flag[i]=0;
            }
        }
}
int main()
{
    int n,m;
    char str[14];
    while(~scanf("%d",&n))
    {
        memset(flag,0,n);//将flag数组初始化为0;
        min=n*n;//min存最少移动次数
        scanf("%s",str);
        find(str,n,0);//最初状态
        if(min==n*n) min=-1;
        printf("%d\n",min);
    }

    return 0;
}

发表于 2019-02-28 14:11:07 回复(2)
#include<stdio.h>
#include<string>
#include<iostream>
#include<map>
#include<queue>
using namespace std;
bool check(string);
struct node{
	string v;
	int step;
	node(string x,int step):v(x),step(step){}
};
int main(){
	int N;
	string x;
	while(cin>>N){
		cin>>x;
		if(N<4){
			printf("-1\n");
			continue;
		}
		map<string,int> book;
		queue<node> Q;
		Q.push(node(x,0));
		int flag=0,step=-1;
		book[x]=1;
		while(!Q.empty()){
			node head=Q.front();Q.pop();
			if(check(head.v)){
				//flag=1;
				step=head.step;
				break;
			}
			string s=head.v;
			for(int i=0;i<=s.length()-2;i++){
				string tmp=s;
				tmp[i]=s[i+1];
				tmp[i+1]=s[i];
				if(book.count(tmp)==0){
					book[tmp]=1;
					Q.push(node(tmp,head.step+1));
				}
			}
		}
		printf("%d\n",step);
	}
}
bool check(string x){
	if(x.length()<4) return false;
	int i;
	for(i=0;i<=x.length()-4;i++)
		if(x[i]=='2'&&x[i+1]=='0'&&x[i+2]=='1'&&x[i+3]=='2')
			return true;
	return false;
}

发表于 2017-08-04 10:22:31 回复(1)
#include <bits/stdc++.h>
using namespace std;
int flag, res, n;
string s;

bool check(string str) {
    for(int i = 0; i <= str.size() - 4; i++) {
        if(str.substr(i, 4) == "2012") {
			return true;
		}
    }
	return false;
}

void bfs() {
	queue<pair<string, int>> q;
	q.push({s, 0});
	while(!q.empty()) {
		auto t = q.front();
		q.pop();
		if(check(t.first)) {
			flag = 1;
			res = t.second;
			break;
		}
		for(int i = 0; i < t.first.size() - 1; i++) {
			swap(t.first[i], t.first[i + 1]);
			q.push({t.first, t.second + 1});
			swap(t.first[i], t.first[i + 1]);
		}
	}
}

int main() {
    int n;
	cin >> n;
    cin >> s;
    bfs();
	if(flag) {
		cout << res << endl;
	} else {
		cout << -1 << endl;
	}
}


发表于 2022-01-05 12:06:00 回复(0)
#include<iostream>
#include<queue>
#include<string>
using namespace std;
struct state
{
	string s;
	int t;
	state(string s,int t):s(s),t(t){}
};
queue<state> que;
void bfs(string s)
{
    state current(s,0);
	que.push(current);
	while(!que.empty())
	{
		state num=que.front();
		que.pop();
		if(num.s.find("2012")) 
		{
			cout<<num.t;
			return;
		} 
		else
		{
            for(int i=0 ; i<num.s.size()-1 ; i++)
            {
                state next(num.s,num.t+1);
                char c=next.s[i];
                next.s[i]=next.s[i+1];
                next.s[i+1]=c;
                que.push(next);
            }
			
		}
	}
    cout<<-1;
}
int main()
{
    string code;
    return 0;
}

BFS做法,用一个结构体记录字符串和当前所用次数,对于长n的字符串有n-1种移动方法,
编辑于 2021-03-09 14:58:51 回复(0)
使用Map可以同时查找当前串是否出现过,同时记录交换的次数
#include<iostream>
#include<cstdio>
#include<queue>
#include<string>
#include<map>
using namespace std;
int num;
std::map<string, int> myMap;
void BFS(string str)
{
	queue<string> myQueue;
	myQueue.push(str);
	myMap[str] = 0;
	while (!myQueue.empty())
	{
		string temp = myQueue.front();
		myQueue.pop();
		if (temp.find("2012") != string::npos)
		{
			cout << myMap.find(temp)->second << endl;
			return;
		}	
		for (int i = 0; i < temp.size() - 1; i++)
		{
			string temp1 = temp;
			char c = temp1[i];
			temp1[i] = temp1[i + 1];
			temp1[i + 1] = c;
			if (myMap.find(temp1) == myMap.end())
			{
				myQueue.push(temp1);
				myMap[temp1] = myMap.find(temp)->second+1;
			}
		}
	}
	cout << -1 << endl;
}
int main()
{
	string str;
    int n;
	while (cin >> n >> str)
	{
		num = 0;
		myMap.clear();
		BFS(str);
	}
	return 0;
}

发表于 2020-06-20 21:00:26 回复(0)
#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
#include<unordered_map>
using namespace std;
/*算法:N叉树层次遍历(BFS)*/
int main()
{
	int N;
	string str;
	queue<string> Q;//BFS队列
	unordered_map<string, bool> mark;//访问过标记,用哈希查询比较快
	while (cin>>N>>str)
	{
		Q.push(str);
		mark[str] = true;
		//l_c:当前层最后一个 l_n:下一层最后一个 current:当前字符串
		string l_c = str, l_n = "", current = str;
		int count = 0;//次数
		//只有当缺0||1||2时才无法解密
		if (str.find('0') == str.npos 
			|| str.find('1') == str.npos 
			|| str.find('2') == str.npos)
			count = -1;
		else
		{
			while (str.find("2012") == str.npos)
			{
				for (unsigned int i = 0; i < N - 1; i++)
				{
					str = current;
					swap(str[i], str[i + 1]);//往右交换相邻字符
					if (mark[str] == false)//没访问过的入队
					{
						Q.push(str);
						mark[str] = true;
						l_n = str;
					}
					else
						continue;
				}
				if (current == l_c)//到达当前层最后一个,就要加一层
				{
					l_c = l_n;
					count++;
				}
				Q.pop();
				str = Q.front();
				current = str;
			}		
		}
		cout << count << endl;
		//多组输入善后
		while (!Q.empty())
				Q.pop();
			mark.clear();
	}
	return 0;
}

.N叉树层次遍历,也叫BFS宽度优先搜索,应该写的比较清晰
编辑于 2020-06-18 14:33:22 回复(0)
J1_头像 J1_
#include <bits/stdc++.h>
using namespace std;

/*
	有连续 2012 -> s.find("2012") != string::npos
	相邻的字符移位 -> swap(s[i-1], s[i])
	统计移位次数 -> map<string, int>
	注意的点:对于2222这样的字符串,其移位后可能会存在相同的字串,要去重 
*/

map<string, int> M;		//M[s] 表示字符串 s 的已移位次数
int BFS(string s) {
	queue<string> Q;
	Q.push(s);
	M[s] = 0;	
	while(!Q.empty()) {
		string current = Q.front();
		if(current.find("2012") != string::npos) {	//若找到,返回移位次数 
			return M[current];
		}
		Q.pop();
		for(int i = 1; i < current.size(); i++) {	//遍历分支 
			string next = current;
			swap(next[i - 1], next[i]);
			if(M.find(next) == M.end()) {	//如果移位后的新字符串还没出现过 
				M[next] = M[current] + 1;	//**则它的移位次数是它父亲的次数+1** 
				Q.push(next);				
			} 
			else {							//若已经出现过,抛弃 
				continue;
			}
		}
	}
	
	return -1;	//无法组成,返回-1 
}

int main() {
	int n;
	string s;
	while(cin >> n >> s) {
		cout << BFS(s) << endl;
	}
}

发表于 2020-04-10 16:36:57 回复(0)
#include<bits/stdc++.h>

using namespace std;


struct Status
{
    string x;
    int t;
    Status(string x1,int t1):x(x1),t(t1) {}
};

string change(string x,int n)
{
    char ch;
    if(n<x.size()-1)
    {
        ch=x[n];
        x[n]=x[n+1];
        x[n+1]=ch;
    }
     return x;  
}

void BFS(string x)
{
   queue<Status>myqueue;
   Status begin(x,0);
   myqueue.push(begin);
   while(!myqueue.empty())
   {
       Status current=myqueue.front();
       myqueue.pop();
       if(current.x.find("2012")!=x.npos)//如果2012在开头那么返回0 得想办法处理
       {
           cout<<current.t;
           break;//找到,那么输出,函数结束
       }
       
       current.t=current.t+1;
       string x=current.x; //必须先记录下来再去循环,否则循环里面不能实现本意
       for(int i=0;i<x.size()-1;i++)//进行广度优先遍历
       {
           current.x=change(x,i);
           myqueue.push(current);
       }
       
   }
}


int main()
{
    int n;
    cin>>n;
    string x;
    while(cin>>x)
        BFS(x);
    return 0;
}

发表于 2020-04-04 20:35:03 回复(0)
//BFS算法
#include <iostream>
(720)#include <algorithm>
#include <map>
(747)#include <queue>
#include <set>

using namespace std;

set<string> str_set;
queue<string> str_queue;

bool in_str(string str)									//判断2012是否在串中
{
	for (int i = 0; i < str.length() - 4; i++)
	{
		if (str.substr(i, 4) == "2012")
			return true;
	}
	return false;
}

string swap_str(string str, int i, int j)				//交换串中i,j位置的值
{
	char temp = str[i];
	str[i] = str[j];
	str[j] = temp;
	return str;
}

int get_times(string str)
{
	int cnt = 0, index = 0;
	if (in_str(str))
		return index;
	else
	{
		str_queue.push(str);
		str_set.insert(str);
	}
	
	bool tag = true;

	while (!str_queue.empty() && tag)
	{
		//cout << "队列长度为:" << str_queue.size() << endl;
		int qu_length = str_queue.size();
		for (int i = 0; i < qu_length; i++)
		{
			string s = str_queue.front();
			str_queue.pop();
			if (in_str(s))
			{
				tag = false;
				index = cnt;
				break;
			}
			for (int j = 0; j < s.length() - 1; j++)
			{
				string swapped_s = swap_str(s, j, j + 1);
				if (str_set.find(swapped_s) == str_set.end())
				{
					str_queue.push(swapped_s);
					str_set.insert(swapped_s);
				}
			}
		}
		cnt++;
	}
	return index;
}

int main()
{
	int n;
	string str;
	while ( cin >> n >> str)
	{
		int valid[3] = { 0 };
		for (auto c : str)
			valid[c - '0']++;
		if (valid[0] >= 1 && valid[1] >= 1 && valid[2] >= 2)
		{
			cout << get_times(str) << endl;
		}
		else
			cout << -1 << endl;
	}
}

发表于 2020-03-22 22:51:51 回复(0)
人生中第一次写BFS,第一次去了解使用map,纪念一下。
谈谈BFS:
1.状态 ( 即问题中让我们干什么,去找什么,本题中就是找一个字符串中有连续的“2012”四个字符,输出移位次数 )
2.状态扩展方式 ( 分析怎么算扩展,本题中就是移位,字符串变了,移位次数也变了 )
3.有效状态 ( 这个有效状态是针对扩展时来说的,有的状态之前已经出现过了,现在出现就重复了,或者有的题目状态出界了,这种要舍弃 )
4.队列 ( BFS借助队列实现,先进入的状态先扩展,不断把有效状态插入队尾,然后取队头再进行扩展 )
5.标记 ( 本题中借助了map来做标记,判断那些状态是有效的,即不是重复出现的 )
6.有效状态数 (这个一般是为了算时间复杂度,一般有效状态数和时间复杂度同数量级,大致算一下会不会超时 )
7.最优 ( BFS宽度优先搜索一般是为了解决最优问题,特性就是状态总是按照某个关键字递增,这样得到的结果一定是最优的 )

#include <bits/stdc++.h>
using namespace std;

struct Code{
    string s;                                            //记录当前的字符串
    int m;                                               //记录当前移位的次数
    Code(string s, int m): s(s), m(m) {}
};

string swap(string nstr, int k){
    char tmp;
    tmp = nstr[k];
    nstr[k] = nstr[k+1];
    nstr[k+1] = tmp;
    return nstr;
}

map<string, bool> visit;                        //用一个 map 记录当前的字符串是否在之前出现过

void BFS(string st){
    queue<Code> Q;
    Q.push(Code(st, 0));                      //压入初始状态,此时结构体中的m = 0(移位 0 次)
    int len = st.size();
    visit[st] = true;
    while(!Q.empty()){
        Code current = Q.front();                              //定义一个结构体 current 表示当前的状态
        Q.pop();
        if(current.s.find("2012") != string::npos){               //当前状态符合题意,也就是找到了
            cout << current.m << endl;                      //输出 current 结构体中的 m,也就是移位的次数
            visit.clear();                   //多次输入一定要 clear,不然会影响下一次输入的结果
            return;
        }
        string str;
        for(int i = 0; i < len - 1; ++i){      //由题意知最多输入13个字符,那最多就有12种移位方式
            Code next(current.s, current.m + 1);   //定义一个结构体next表示当前状态的下一状态,注意区别就是移位次数 +1 了
            if(i == 0){
                str = swap(next.s, 0);
            }
             else if(i == 1){
                str = swap(next.s, 1);
            }
             else if(i == 2){
                str = swap(next.s, 2);
            }
             else if(i == 3){
                str = swap(next.s, 3);
            }
             else if(i == 4){
                str = swap(next.s, 4);
            }
             else if(i == 5){
                str = swap(next.s, 5);
            }
             else if(i == 6){
                str = swap(next.s, 6);
            }
             else if(i == 7){
                str = swap(next.s, 7);
            }
             else if(i == 8){
                str = swap(next.s, 8);
            }
             else if(i == 9){
                str = swap(next.s, 9);
            }
             else if(i == 10){
                str = swap(next.s, 10);
            }
             else if(i == 11){
                str = swap(next.s, 11);
            }
            next.s = str;
            if(visit[next.s] == true){            //判断当前的字符串是否出现过
                continue;                     //出现过就不把当前字符串压入队列(无效状态)
            }
            Q.push(next);                         //没出现过把新的字符串压入队列(新的有效状态)
            visit[next.s] = true;                //新的字符串现在出现过了,map 中设为 true
        }
    }
    visit.clear();                          //多次输入一定一定要 clear,不然下面的输入输出结果永远是 -1
    cout << "-1" << endl;                   //所有有效状态遍历完了,还是没有合格的,输出 -1
}

int main(){
    int n;
    string str;
    while(cin >> n){
        cin >> str;
        BFS(str);                           //人生的第一个BFS,通过的瞬间好爽
    }
    return 0;
}

编辑于 2020-03-21 13:30:19 回复(0)

满满的成就感,没看过评论区,从一开始尝试递归(发现走不通)到仅靠bfs(发现空间复杂度太大),再经过不断的优化,自己实现了bfs+map,然后再看评论区,发现英雄所见略同,太爽了!!收获:以后遇到不会的,多想多尝试,否则很容易养成一种 一不会就看解题报告 的陋习,大家加油~
#include <bits/stdc++.h>
(755)#include <queue>
using namespace std;
int n;
map<string,bool>m;
typedef struct {
	string s;
	int depth;
} tree;

bool isTrue(tree str) {

		for(int i=0; i<=n-4; i++) {
			if(str.s.substr(i,4)=="2012") {
				return true;
			}
		}
		return false;

}
string ownswap(tree str,int x,int y ) {
	char tmp=str.s[x];
	str.s[x]=str.s[y];
	str.s[y]=tmp;
	return str.s;
}
int main() {
	queue<tree>q;

	//int flag=0;
	tree str,tmp;
	cin>>n>>str.s;
	str.depth=0;
	m[str.s]==true;
	q.push(str);
	while(!q.empty()) {
		tmp=q.front();
		if(isTrue(tmp)) {
			cout<<tmp.depth<<endl;
			break;
		}
		//flag++;
		q.pop();
		for(int i=0; i<n-1; i++) {
			tree tmp1;
			tmp1.s=ownswap(tmp,i,i+1);
			tmp1.depth=tmp.depth+1;
			if(m[tmp1.s]==true) continue;
			else{
				m[tmp1.s]=true;
				q.push(tmp1);
			}
			
			
		}

	}
	return 0;
}

编辑于 2020-03-19 17:21:35 回复(0)
#include<iostream>
(720)#include<cstdio>
#include<map>
(747)#include<cstring>
#include<queue>
using namespace std;
map<string,int> visit;
int BFS(int n,string s){
    queue<string>    Q;
    Q.push(s);
    visit[s]=1;
    while(!Q.empty()){
        string temp=Q.front();
        Q.pop();
        if(temp.find("2012",0)!=string::npos)
            return visit[temp]-1;
        for(int i=0;i<n-1;i++){
            string str=temp;
            swap(str[i],str[i+1]);
            if(visit[str]!=0)    continue;
            else{
                Q.push(str);
                visit[str]=visit[temp]+1;
            }
        }
    }
    return -1;
}
int main(){
    int N;
    string input;
    while(scanf("%d",&N)!=EOF){
        cin>>input;
        printf("%d\n",BFS(N,input));
    }
    return 0;
}
自己写的,没有参考,应该比较清楚了吧
发表于 2020-03-17 11:18:46 回复(0)
#include <bits/stdc++.h>
using namespace std;
struct code{
	string code_str;
	int step;
};
int getStep(string str,int n){
	vector<code> vi;
	int index=0; //step代表当前字符串是交换了几次的结果,初始值为0,因为可能存在一开始就有2012 
	code c;
	c.step=0;
	c.code_str=str;
	vi.push_back(c); //初始化 
	//开始只想到了全排列,所以跳出的条件是 pow(3,n) 比如 长度为4的串,最多有 3的四次方个排列 .
	//看完讨论后才知道是BFS,哈哈 ,用队列比较好 
	while(vi.size()<pow(3,n)){ 
		if(vi[index].code_str.find("2012")!=-1){
			return vi[index].step;
		}else{
			string tem;
			tem=vi[index].code_str;
			for(int i=0;i<n-1;i++){ //没找到 那么只能由当前的字符串交换一次后所有结果加进去,在加的时候顺便判读一下是否有了 2012 
				swap(tem[i],tem[i+1]);
				code next;
				next.code_str=tem;
				next.step=vi[index].step+1;
				if(tem.find("2012")!=-1){ // 在加的时候顺便判读一下是否有了 2012 
					return next.step;
				}
				vi.push_back(next);
				tem=vi[index].code_str;
			}
			index++;
		}
	}
	return -1;
}
int main(){
	int n;
	string str;
	
	while(cin>>n>>str){
		if(n<4){
			cout<<-1<<endl;
		}else{
			cout<<getStep(str,n)<<endl;
		}
	}
	return 0;
}


发表于 2020-03-11 17:32:18 回复(0)
/*
    考察BFS 
*/
#include <bits/stdc++.h>
using namespace std;
map<string,int> visit; // 标记数组,并且还能还能表示交换次数
string swap(string str,int x,int y){ // 交换字符串x,y位置的字符
	char temp = str[x];
	str[x] = str[y];
	str[y] = temp;
	return str;	
} 
int BFS(string str){
	visit.clear(); // 每次标记数组都要清0
	queue<string> myQueue;
	myQueue.push(str);
	visit[str] = 0; // 第一次进来交换次数为0
	while(!myQueue.empty()){ // 队列非空时才进行
		string cur = myQueue.front();
		myQueue.pop();
		if(cur.find("2012")!=string::npos){ // 如果当前直接就找到了,那么直接返回
			return visit[cur];
		}else{
			for(int i = 0;i<cur.size()-1;i++){
				string temp = swap(cur,i,i+1);
				if(visit.find(temp)==visit.end()){ // 如果不在标记中,即之前没有出现过,才入队
					myQueue.push(temp);
					visit[temp] = visit[cur]+1; // 交换次数是上一层的次数+1
				}
			}
		}
	}
	return -1; // 走完所有可能都没有找到,返回-1
}

int main(){
	int n; // n的意义不明
	string str;
	while(cin>>n>>str){
		cout<<BFS(str)<<endl;
	}
	return 0;
}

编辑于 2020-03-10 20:51:14 回复(0)