Sliding Puzzle II – Python 3 (Week 12 – 14)

class Solution:
    """
    @param init_state: the initial state of chessboard
    @param final_state: the final state of chessboard
    @return: return an integer, denote the number of minimum moving
    """
    def minMoveStep(self, init_state, final_state):
        # # write your code here
        st, ed = "", ""
        for i in range(3):
            for j in range(3):
                st += str(init_state[i][j])
                ed += str(final_state[i][j])
        step = 0
        fx = [0,0,1,-1]
        fy = [1,-1,0,0]
        q = collections.deque()
        v = set()
        q.append(st)
        v.add(st)
        step = 0
        while q:
            step += 1
            size = len(q)
            print(step)
            for i in range(size):
                now = q.popleft()
                index0 = now.find('0')
                x0, y0 = index0 // 3, index0 % 3
                print(x0)
                print(y0)
                for j in range(4):
                    nx, ny = x0 + fx[j], y0 + fy[j]
                    if nx < 0 or nx >= 3 or ny < 0 or ny >= 3:
                        continue
                    indexchange = nx * 3 + ny
                    a, b = max(index0, indexchange), min(index0, indexchange)
                    current = now[0:b] + now[a] + now[b + 1:a] + now[b] + now[a + 1:]
                    if current not in v:
                        if current == ed:
                            return step
                        v.add(current)
                        q.append(current)
            
        return -1