leetcode 滑动谜题

滑动谜题

在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示.

一次移动定义为选择 0 与一个相邻的数字（上下左右）进行交换.

最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。

给出一个谜板的初始状态，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/sliding-puzzle 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

广度

bsf

def tostr(board):
    ret = ''
    for i in range(len(board)):
        for j in range(len(board[0])):
            ret += str(board[i][j])
    return ret


def f(board):
    xxx = {0:[1,3], 1: [0,2,4], 2: [1,5], 3: [0,4], 4: [1,3,5], 5:[2,4]}
    seen = set()
    queue = [(tostr(board), 0)]
    ans = float('inf')

    while queue:
        s,count = queue.pop(0)
        if s == "123450":
            ans = min(ans, count)
        if s in seen:
            continue
        seen.add(s)
        s = list(s)
        pos_0 = s.index('0')
        for i in xxx[pos_0]:
            s[pos_0], s[i] = s[i], s[pos_0]
            queue.append((''.join(s), count + 1))
            s[pos_0], s[i] = s[i], s[pos_0]

    if ans == float('inf'):
        return -1
    return ans