首页 > 试题广场 >

密码锁

[编程题]密码锁

热度指数：4262 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

玛雅人有一种密码，如果字符串中出现连续的2012四个数字就能解开密码。给一个长度为N的字符串（2=<N<=13），该字符串中只含有0,1,2三种数字，问这个字符串要移位几次才能解开密码，每次只能移动相邻的两个数字。例如02120经过一次移位，可以得到20120,01220,02210,02102，其中20120符合要求，因此输出为1.如果无论移位多少次都解不开密码，输出-1。

输入描述:

第一行输入N，第二行输入N个数字，只包含0，1，2

输出描述:

输出字符串要移几位才能解开密码，如果无论移位多少次都解不开密码，输出-1

示例1

输入

输出

1
1

算法知识视频讲解

Python

刘三省

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

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

发表于 2020-01-05 12:33:15 回复(1)