[数据结构与算法]蓝桥杯：卡片换位（BFS）Python实现

题目描述

这题应该是一个经典的BFS，一开始根本没有思路，看了题解，发现大佬们做的时候都是以“空格”为移动对象，于是我也这么做
定眼一看，二维数组嘛~但是跟着大佬走学了新的一招，将一维数组转成二维数组，将二维数组转成一维数组
一维转二维：xn = index//3，yn = index%3
二维转一维:index = xn * 3 + yn
步数怎么记录呢？用一个字典吧，每次走一步都在上一步加一，key就是“状态”
PS：这个题有地方很怪，至少我是看了案例才知道的，有一个案例是根本没有空格这个元素的，所以（至少）我用Python没有保证全过，作了一下弊，看了答案，写了个异常处理，姑且100分（不然会有一个无效返回的错误，87分）

代码实现

import collections

dir = [[0, 1], [1, 0], [0, -1], [-1, 0]]  # 右下左上
dic = {}


def bfs():
    """
    切换一维数组和二维数组，找到S中A和B交换位置的一种可能性，用字典保存在S’下的走的步数
    :return: 输出当前S下的走的步数，步数从0开始
    """
    que = collections.deque()
    que.append(S)
    dic[S] = 0
    while que:
        now = list(que.popleft())
        if now.index('A') == indexB and now.index('B') == indexA:  # 发现当前S'的A和B是交换位置的，就输出到now这个位置走的步数
            return dic["".join(now)]
        try:
            space = now.index(" ")  # 空格的位置，这里主要是从空格开始向周围移动
        except:
            return 10
        x, y = space // 3, space % 3  # 这里将S这个一维数组变成了二维数组，xn和yn是在这个二维数组下的左边，实际上这个二维数组并不存在
        distance = dic["".join(now)]  # 记录知道当前模式下需要的步数,为了在以此模式为基础的新模式的步数做+1准备
        for i in range(4):
            xn, yn = x + dir[i][0], y + dir[i][1]
            if xn in [0, 1] and yn in [0, 1, 2]:
                keynow = now.copy()  # 因为后面需要修改空格和下一个移动的位置，所以先copy一个，不然还要把移动的now返回，这样添加在que里的now也是错的，所以换成keynow代替now移动
                keynow[space], keynow[xn * 3 + yn] = keynow[xn * 3 + yn], keynow[space]  # now是一维的数组，要将xn和yn变成一维的样子
                if not dic.__contains__("".join(keynow)):  # 经过上面的交换，now已经有了变换，变成了新的状态
                    dic["".join(keynow)] = distance + 1  # 记录now的新状态走的步数
                    que.append(keynow)  # 为了在新的位置now下继续寻找答案，加入到que里，其实和普通的bfs一样意思
    return -1


if __name__ == '__main__':
    s1 = input()
    s2 = input()
    S = s1 + s2
    indexA = S.index('A')
    indexB = S.index('B')
    print(bfs())

至于为什么Python过不了没有空格的案例，我不知道是因为啥，难道是案例错了？