滑动谜题 -- BFS

滑动谜题

输入：board = [[4,1,2],[5,0,3]]
输出：5
解释：
最少完成谜板的最少移动次数是 5 ，
一种移动路径:
尚未移动: [[4,1,2],[5,0,3]]
移动 1 次: [[4,1,2],[0,5,3]]
移动 2 次: [[0,1,2],[4,5,3]]
移动 3 次: [[1,0,2],[4,5,3]]
移动 4 次: [[1,2,0],[4,5,3]]
移动 5 次: [[1,2,3],[4,5,0]]

class SlidingPuzzle:
    """
    773. 滑动谜题
    https://leetcode.cn/problems/sliding-puzzle/
    """
    def solution(self, board: List[List[int]]) -> int:
        """

        :param board:
        :return:
        """
        m, n = len(board), len(board[0])
        target = '123450'
        start = ''
        for i in range(m):
            for j in range(n):
                start += str(board[i][j])

        # BFS算法 框架开始
        queue = []
        visited = set()
        step = 0
        nei_map = self.generateNeighborMapping(m, n)
        # 从起点开始BFS搜索
        queue.append(start)
        visited.add(start)

        while queue:
            sz = len(queue)
            for i in range(sz):
                cur = queue.pop(0)
                if cur == target:
                    return step

                idx = 0
                for _ in cur:
                    if cur[idx] == '0':
                        break
                    idx += 1

                for adj in nei_map[idx]:
                    new_board = self.swap(cur, adj, idx)
                    if new_board not in visited:
                        queue.append(new_board)
                        visited.add(new_board)
            step += 1

        return -1

    def generateNeighborMapping(self, m, n):
        """
        给定一个二维m*n数组，返回每个节点的邻居节点，用一维数组表示
        :param m:
        :param n:
        :return:
        """
        res = []
        for i in range(m*n):
            tmp = []
            # 如果i不是第一列，那么有左侧邻居
            if i % n != 0:
                tmp.append(i-1)

            # 如果i不是最后一列，那么有右侧邻居
            if i % n != n-1:
                tmp.append(i+1)

            # 如果i不是第一行，那么有上侧邻居
            if i - n >= 0:
                tmp.append(i-n)

            # 如果i不是最后一行，那么有下侧邻居
            if i + n < m*n:
                tmp.append(i+n)

            res.append(tmp)

        return res

    def swap(self, cur, idx, adj):
        cur_arr = list(cur)
        tmp = cur_arr[idx]
        cur_arr[idx] = cur_arr[adj]
        cur_arr[adj] = tmp
        return ''.join(cur_arr)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88