密码锁

这道题跟玛雅人那道题一样，但测试用例似乎有点问题。

def BFS(Q,k,n,trash):
    m = len(Q)
    for j in range(m):
        q = Q.pop(0)
        trash.append(q)
        for i in range(n-1):          
            if '2012' in q[:i]+q[i+1]+q[i]+q[i+2:]:
                return k+1
            else:
                if q[:i]+q[i+1]+q[i]+q[i+2:] not in Q+trash:
                    Q.append(q[:i]+q[i+1]+q[i]+q[i+2:])
    return BFS(Q,k+1,n,trash)

while True:
    try:
        n = int(input())
        s = input()
        trash = []
        char_cnt = {'0':0,'1':0,'2':0}
        for i in range(n):
            char_cnt[s[i]] += 1
        if char_cnt['0']<1 or char_cnt['1']<1 or char_cnt['2']<1:
            print(-1)
        elif '2012' in s:
            print(0)
        else:
            print(BFS([s],0,n,trash))
    except:
        break

//看了好久了没看出哪里有问题，烦请各位大佬帮忙指摘下，不胜感激啊
//思路是bfs

#include<iostream>
#include<string>
#include<queue>
#include<set>
using namespace std;

struct ele{
    string s;//对应的string
    int cnt;//由init的string经过ct次移位得到的
    ele(){}
    ele(string ss, int cc):s(ss), cnt(cc){}
};

int istrue(string s){
    if(s.find("2012")!=-1){
        return 1;
    }else{
        return 0;
    }
}

int main(){
    string s;
    int len, ct, i;
    while(cin>>len){
        cin>>s;
        //初步判断 不含有0 1 两个2
        if(s.size()<4 || s.find("0")==-1 || s.find("1")==-1 || s.find("2")==-1){
            cout<<-1<<endl;
            continue;
        }
        ct=0;
        for(i=0; i<len; i++){
            if(s[i]=='2')
                ct++;
        }
        if(ct<2){
            cout<<-1<<endl;
            continue;
        }

        ct=0;//记录移位次数
        queue<ele> q;
        q.push(ele(s, ct));
        string tp;
        ele e;
        int flag=0;
        set<string> st;

        while(!q.empty()){
            e=q.front();
            q.pop();
            if(st.count(e.s)){//访问过的不再访问了，记录的是相同string的情况下移位次数最少的那个
                continue;
            }else{
                st.insert(e.s);
            }

            if(istrue(e.s)){
                cout<<e.cnt<<endl;
                flag=1;
                break;
            }

            ct++;//移位
            for(i=0; i<e.s.size()-1; i++){
                tp=e.s;
                swap(tp[i], tp[i+1]);
                q.push(ele(tp, ct));
            }
        }
        if(flag==0){
            cout<<-1<<endl;
        }
    }
    return 0;
}

#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
struct N{    //转移状态
    string str;
    int t;    //转换次数
};
queue<N> Q;
map<string,int> M;
bool IsInMap(string s){    //s是否在map中
    if(M.find(s)==M.end()){
        M[s]=0;        //不在则插入
        return false;
    }
    else return true;
}
bool IsSolve(string s){
    if(s.find("2012",0)!=string::npos) return true;
    else return false;
}
void BFS(int n){    //n为字符串长度
    while(!Q.empty()){    //Q非空
        N nown=Q.front();
        Q.pop();
        string temp;
        for(int i=0;i<n-1;i++){
            temp=nown.str;    //取出当前状态
            swap(temp[i],temp[i+1]);    //交换
            if(IsInMap(temp)) continue;    //交换之后在map中已经存在了
            if(IsSolve(temp)){        //当前状态是目标
                cout<<nown.t+1<<endl;return;
            }
            //其他状态，入队
            N newn;
            newn.str=temp;newn.t=nown.t+1;
            Q.push(newn);
        }
    }
    cout<<-1<<endl;
}
int main(){
    int l;
    string str;
    while(cin>>l){
        while(!Q.empty()) Q.pop();
        M.clear();
        cin>>str;
        if(IsSolve(str)) cout<<0<<endl;    //不用转换
        else{
            M[str]=0;
            N f;
            f.str=str;f.t=0;
            Q.push(f);
            BFS(l);
        }
    }
}

#include <iostream>
#include <queue>
#include <set>
#include <string>
using namespace std;

struct Node {
    string str; //字符串
    int depth;  //移位次数（广度优先搜索的深度）
    Node(string str, int depth): str(std::move(str)), depth(depth) {}
};

//判断字符串是否含有“2012”这几个字符
bool contain2012(string str) {
    if (str.length() < 4) {
        return false;
    }
    int count0 = 0,
        count1 = 0,
        count2 = 0; //统计‘0’、‘1’、‘2’字符的个数
    for (const auto& ch : str) {
        count0 += ch == '0';
        count1 += ch == '1';
        count2 += ch == '2';
    }
    return count0 >= 1 && count1 >= 1 && count2 >= 2;
}

//交换字符串str中下标为index和index+1的相邻字符
string swap_char(string str, int index) {
    swap(str[index], str[index + 1]);
    return str;
}

int main() {
    int n;
    string str;
    while (cin >> n >> str) {
        if (!contain2012(str)) {    //无解
            cout << -1 << endl;
            continue;
        }
        if (str.find("2012") != string::npos) { //无需移位
            cout << 0 << endl;
            continue;
        }
        queue<Node>myQueue;     //用于广度优先搜索的队列
        set<string>visited;     //标记已访问的字符串
        myQueue.push({str, 0});
        visited.insert(str);
        while (!myQueue.empty()) {
            Node current = myQueue.front();
            myQueue.pop();
            string str = current.str;
            int depth = current.depth + 1;
            for (int i = 0; i < n - 1; i++) {
                string str1 = swap_char(str, i);
                if (str1.find("2012") != string::npos) {
                    cout << depth << endl;
                    goto exit;  //作用相当于多重循环的break
                }
                if (visited.find(str1) == visited.end()) {
                    myQueue.push({str1, depth});
                    visited.insert(str1);
                }
            }
        }
exit:       //终止多重循环的出口
        ;
    }
    return 0;
}

#include<iostream>
#include<cstdio>
#include<string>
#include<queue>
#include<map>
using namespace std;

struct code {
	string name;
	int num;
	code(string na,int n):name(na),num(n){}
};


int BFS(string str)
{
	map<string, bool> string_num;
	queue<code> q;
	q.push(code(str, 0));
	string_num[str] = true;
	while (!q.empty())
	{
		code current = q.front();
		q.pop();
		if (current.name.find("2012")!=string::npos)
		{
			return current.num;
		}
		for (int i = 0;i < current.name.size() - 1;i++)
		{
			{
				string next=current.name;
				swap(next[i], next[i + 1]);
				if (string_num.find(next) != string_num.end() && string_num[next]);
				else
				{
					q.push(code(next, current.num + 1));
					string_num[next] = true;
				}
			}
		}
	}
	return -1;
}


int main()
{
	string str;
	int n;
	while (cin >> n >> str)
	{
		printf("%d\n", BFS(str));
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;
const int N=15;
int n;
string s;
bool st[N];
int minstep=1e9;
//dfs做***超时，对使用未超时的测试用例均正确
void dfs(int u, int step)
{
    if(u>n-1) return ;
    if(s.find("2012")!=-1)
    {
        minstep=min(minstep, step);
        return;
    }
        
    for(int i=0;i<s.size()-1;i++)
    {
        if(!st[i])
        {
            st[i]=true;
            swap(s[i],s[i+1]);
            dfs(u+1,step+1);
            swap(s[i],s[i+1]);
            st[i]=false;
        }
    }
}

int main()
{
    
    while(cin>>n>>s){
        
        memset(st, 0, sizeof st);
        minstep=1e9;
        dfs(0,0);
        if(minstep==1e9)
            cout<<-1<<endl;
        else
            cout<<minstep<<endl;
    }
    
   
    return 0;
}

#include <iostream>
#include<queue>
#include<map>
using namespace std;

typedef struct Node{
    string str;//当前字符串
    int step;//第几次移位
}Node;

int bfs(string str){//广度优先
    queue<Node> q;//广度优先队列
    map<string,bool> visited;//该某字符是否被搜索过
    Node node;
    node.str=str;
    node.step=0;//第一个字符串移位次数为0
    q.push(node);
    int step=-1;//解不开密码的默认返回
    while(!q.empty()){//队列非空
        Node temp=q.front();//队头元素
        q.pop();
        string s=temp.str;//当前检查的字符串
        visited[s]=true;//令该字符串在map中有记录
        if(s.find("2012")==s.npos){//若当前字符串不包含2012
            for(int i=0;i<s.size()-1;i++){//进行n-1次交换
                swap(s[i],s[i+1]);//移位
                if(visited.find(s)==visited.end()&&visited[s]!=true){//移位后的字符串没有被访问过,要么没有加入map，要么不为true
                    Node x;
                    x.str=s;
                    x.step=temp.step+1;//次数加1
                    q.push(x);//入队
                }
                swap(s[i],s[i+1]);//还原
            }
        }else{
            step=temp.step;//找到目标字符串
            break;//注意找到后要终止循环
        }
    }
    return step;
}
int main()
{
    int n;
    while(cin>>n){
        string str;
        cin>>str;
        cout<<bfs(str)<<endl;//广度优先遍历
    }
    return 0;
}

from collections import deque
from copy import deepcopy


def switcher(s,level):
    ss = []
    for i in s:
        ss.append(i)
    
    result = []
    for i in range(len(ss)-1):
        new_one = deepcopy(ss)
        new_one[i+1] = ss[i]
        new_one[i] = ss[i+1]
        
        new_s = ''.join(new_one)
        result.append( (new_s,level+1) )
    return result
while True:
    try:
        m = input()
        orig_s = input().strip()
        if '2012' in orig_s:
            print(0)
            continue
        q = deque([])
        used = set()
        q.extend(switcher(orig_s,0))
        used.add(orig_s)
        #print(orig_s)
        while len(q) != 0:
            #print(q)
            one,level = q.popleft()
            if one in used:
                continue
            else:
                if '2012' in one:
                    print(level)
                    break
                else:
                    q.extend(switcher(one,level))
                    used.add(one)
        else:
            print(-1)
    except:
        break

#include <cstdio>
#include <set>
#include <queue>
#include <string>
#include <map>

using namespace std;
set<string> already;
queue< pair<string, int> > q;
const string target("2012");
int n;

string exchangee(const string& s, int pos)
{
	string ret(s);
	auto t = ret[pos];
	ret[pos] = ret[pos-1];
	ret[pos-1] = t;
	return ret; 
}
void init()
{
	already.clear();
	while(!q.empty()) q.pop();
}
void BFS(const string& s0)
{
	q.push(make_pair(s0, 0));
	already.insert(s0);
	while(!q.empty())
	{
		auto now = q.front(); q.pop();
		string nows = now.first;
		if(nows.find(target) != nows.npos)
		{
			printf("%d\n", now.second,nows.c_str());
			return;
		}
		for(auto i = nows.size()-1; i > 0; --i)
		{
			auto te = exchangee(nows, i);
			{
				if(already.insert(te).second)
				{
					q.push(make_pair(te, now.second+1));	
				}	
			}	
		}	
	}
	printf("-1\n");
}
int main()
{
	while(scanf("%d", &n) != EOF)
	{
		if(n==0) break;
		init();
		string si;
		si.clear();
		getchar();
		for(int i = 0; i<n;++i)
		{
			char temp;
			scanf("%c", &temp);
			si.push_back(temp);
		}
		getchar();
		BFS(si);
	}
 } 

#include<bits/stdc++.h>
using namespace std;
struct node{
    string s;
    int t;
    bool operator<(const node &rs)const{//步数少的在优先队列前面。
        return t>rs.t;
    }
};
string str;
int bfs(){
    priority_queue<node>q;
    map<string,int>mp;
    mp[str] = 1;
    q.push({str,0});
    while(!q.empty()){
        node now = q.top();q.pop();
        if(now.s.find("2012")!=string::npos){
            return now.t;
        }
        for(int i = 0;i<now.s.size()-1;i++){
            swap(now.s[i],now.s[i+1]);
            if(mp.count(now.s)){
                swap(now.s[i],now.s[i+1]);
                continue;
            }
            mp[now.s] = 1;
            q.push({now.s,now.t+1});
            swap(now.s[i],now.s[i+1]);
        }
    }
    return -1;
}
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        cin>>str;
        printf("%d\n",bfs());
	}
}

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            //移位
        	int n=sc.nextInt();
        	String code=sc.next();
        	int moveTime=getMoveTime(code);
        	System.out.println(moveTime);
        	
        }
    }

	private static int getMoveTime(String code) {
		if(code.length()<4)return -1;
		List<String>record=new ArrayList<>();//记录已经交换过的结果，剪枝。
		Queue<Help>queue=new LinkedList<>();
		Help help=new Help(code,0);
		queue.offer(help);
		record.add(code);
		while(!queue.isEmpty()) {
			help=queue.poll();
			if(help.s.contains("2012"))
				return help.cnt;
			for(int i=0;i<code.length()-1;i++) {
				char[]arr=help.s.toCharArray();
				char temp = arr[i];
		        arr[i] = arr[i+1];
		        arr[i+1] = temp;
		        String after=new String(arr);
		        if(!record.contains(after)) {
		        	record.add(after);
		        	queue.offer(new Help(after,help.cnt+1));
		        }
			}
		}
		return -1;
	}
}
class Help{
	String s;
	int cnt;
	Help(String s,int cnt){
		this.s=s;
		this.cnt=cnt;//交换次数
}

#include <iostream>
(720)#include <vector>
#include <map>
(747)#include <algorithm>
#include <iterator>
(2102)#include <cmath>
#include <set>
(855)#include <cstdio>
#include <cstdlib>
(895)#include <stack>
#include <queue>
(789)#define PI acos(-1)
using namespace std;

typedef struct Node{
    string state="";//状态
    //int id;//标识
    int t=0;//移动次数
}Node;
int fun(string str){
    //根据输入的str，以三进制的形式输出其对应的数值
    int id=0;
    int l=str.length();
    int i;
    int x;
    for(i=0;i<l;i++){
        x=str[i]-'0';
        id+=x*pow(3,l-i-1);
    }
    return id;
}

int BFS(string str){
    //采用广度优先搜索得到结果
    int l=str.length();//获取字符串长度
    if(str.find("2012")<l)return 0;
    int sizes=pow(3,l);//标技数组的长度
    int i;
    bool mark[sizes];
    for(i=0;i<sizes;i++){
        mark[i]=false;//该状态未被使用
    }
    queue<Node>q;//状态队列
    Node first;
    first.t=0;
    first.state=str;
    int id=fun(str);
    mark[id]=true;
    q.push(first);
    while(!q.empty()){
        //队列不为空
        Node now=q.front();//出队列
        q.pop();//出队列
        //cout<<now.state<<"出队列"<<endl;
        //状态扩展,任意交换相邻的两个字符
        for(i=0;i<l-1;i++){
            string nextstate=now.state;
            char ctmp=nextstate[i];
            nextstate[i]=nextstate[i+1];
            nextstate[i+1]=ctmp;//交换
            int nextt=now.t+1;
            int isexit=nextstate.find("2012");
            if(isexit!=-1){
                //目标状态
                return nextt;
            }
            int nextid=fun(nextstate);//计算状态值
            if(mark[nextid])continue;//说明该状态已经遍历过
            Node next;//构造新状态
            next.state=nextstate;
            next.t=nextt;
            q.push(next);
            //cout<<nextstate<<"入栈"<<endl;
            mark[nextid]=true;
        }
    }
    //直到队列为空都没能找到目标状态，则说明不存在
    return -1;
}
int main(){
    int n;
    string str;
    while(cin>>n){
        cin>>str;
        int ans=-1;
        int i;
        int znum=0;
        int onum=0;
        int tnum=0;
        for(i=0;i<str.length();i++){
            if(str[i]=='0'){
                znum++;
            }else if(str[i]=='1'){
                onum++;
            }else if(str[i]=='2'){
                tnum++;
            }
        }
        if(onum>=1&&znum>=1&&tnum>=2){
            //先做一个简单的排除，如果字符串中含有的0,1,2不能满足2012，直接排除
            ans=BFS(str);
        }else{

        }
        cout<<ans<<endl;
    }
    return 0;
}

#include <iostream>
#include <queue>
#include <string>
#include <unordered_set>
using namespace std;

/*
思路：BFS
*/
//当前str一次变化后字符串vec
vector<string> nextChangeStrVec(string str) {
    vector<string> results;
    for (int i = 1; i < str.size(); i++) {
        swap(str[i], str[i - 1]);
        results.push_back(str);
        swap(str[i], str[i - 1]);        
    }

    return results;
}

int main() {
    int n;
    while (cin >> n) {
        string str;
        cin >> str;
        queue<string> que;
        unordered_set<string> set; //标记str是否已经处理过
        que.push(str);
        set.insert(str);

        int change = 0;
        int flag = 0; //是否找到第一个2012
        while (!que.empty()) {
            if (flag)
                break;

            int size = que.size(); //由于size动态变化，先取出值
            ++change; //每层结果+1
            //分层
            for (int i = 0; i < size; i++) {
                string front = que.front();
                que.pop();

                if (front.find("2012") != -1) {
                    flag = 1;
                }

                vector<string> nexts = nextChangeStrVec(front);
                for (auto str: nexts) {
                    if (set.find(str) != set.end())
                        continue;

                    que.push(str);
                    set.insert(str);
                }
            }
        }

        if (flag)
            cout << change - 1 << endl;
        else
            cout << -1 << endl;
    }
}

//BFS AK!!
#include <iostream>
#include <queue>
#include <string>
#include <map>
using namespace std;

struct Node{
    string str;
    int level;

};

bool check(string str){
    return (str.find("2012",0)!=string::npos);
}

map<string,bool>M;
queue<Node>Q;
int main()
{
    int n;
    string str;
    int ans=0;
    bool flag=false;
    while(cin>>n){
        flag=false;
        ans=0;
        cin>>str;
        while(!Q.empty())Q.pop();
        M.clear();

        Node tmp;
        tmp.str=str;tmp.level=0;
        M[str]=true;
        Q.push(tmp);

        while(!Q.empty()){
            tmp=Q.front();
            Q.pop();
            if(check(tmp.str)){
                ans=tmp.level;
                flag=true;
                break;

            }
            for(int i=0;i<n-1;i++){//两两交换位置
                swap(tmp.str[i],tmp.str[i+1]);
                if(!M[tmp.str]){
                    tmp.level+=1;
                    Q.push(tmp);
                    M[tmp.str]=true;

                    tmp.level-=1;//再变回来
                }
                swap(tmp.str[i],tmp.str[i+1]);//换回来
            }

        }
        if(flag)cout<<ans<<endl;
        else cout<<-1<<endl;

    }
    return 0;
}