There are n cities connected by m flights. Each fight starts from city u and arrives at v with a price w.

Now given all the cities and fights, together with starting city src and the destination dst, your task is to find the cheapest price from src to dst with up to k stops. If there is no such route, output -1.


Example 1:
Input: 
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
Output: 200
Explanation: 
The graph looks like this:


The cheapest price from city 0 to city 2 with at most 1 stop costs 200, as marked red in the picture.


Example 2:
Input: 
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0
Output: 500
Explanation: 
The graph looks like this:


The cheapest price from city 0 to city 2 with at most 0 stop costs 500, as marked blue in the picture.

Note:


       The number of nodes n will be in range [1, 100], with nodes labeled from 0 to n - 1.
       The size of flights will be in range [0, n * (n - 1) / 2].
       The format of each flight will be (src, dst, price).
       The price of each flight will be in the range [1, 10000].
       k is in the range of [0, n - 1].
       There will not be any duplicated flights or self cycles.

Difficulty: interview

Starter code:

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
        

Solutions:
import collections
 
 solved_boards = {((1,2,3),(4,5,0)): 0}
 class Solution:
     def slidingPuzzle(self, board):
         """
         :type board: List[List[int]]
         :rtype: int
         """
         asked = tuple(tuple(row) for row in board)
         queue = collections.deque([((1,2,3),(4,5,0))])
         while queue:
             tboard = queue.popleft()
             for next_board in next_boards(tboard):
                 if next_board in solved_boards:
                     continue
                 solved_boards[next_board] = solved_boards[tboard] + 1
                 queue.append(next_board)
         return solved_boards.get(asked, -1)
     
 def next_boards(board):
     board = [list(row) for row in board]
     zy, zx = find_zero(board)
     for dy, dx in ((-1, 0), (0, 1), (1, 0), (0, -1)):
         nzy, nzx = zy + dy, zx +dx
         if nzy in range(2) and nzx in range(3):
             board[zy][zx],board[nzy][nzx] = board[nzy][nzx],board[zy][zx]
             yield tuple(tuple(row) for row in board)
             board[zy][zx],board[nzy][nzx] = board[nzy][nzx],board[zy][zx]
 
 def find_zero(board):
     for y, row in enumerate(board):
         for x, e in enumerate(row):
             if e == 0:
                 return y,x

import heapq
 class Solution:
     def tupletize(self, board):
         return  tuple(tuple(row) for row in board)
     
     def slidingPuzzle(self, board):
         """
         :type board: List[List[int]]
         :rtype: int
         """
         heap = [(0, self.tupletize(board))]
         visited = set()
         target = ((1,2,3), (4,5,0))
         while heap:
             new_q = []
             for dist, b in heap:
                 if b in visited:
                     continue
                 visited.add(b)
                     
                 if b == target:
                     return dist
                 
                 x = None
                 y = None
                 for i in range(len(b)):
                     if x is not None: break
                     for j in range(len(b[i])):
                         if b[i][j] == 0:
                             x = i
                             y = j
                             break
                             
                 for dx, dy in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
                     if dx >= 0 and dy >= 0 and dx < len(board) and dy < len(board[dx]):
                         newboard = list(list(row) for row in b)
                         newboard[dx][dy], newboard[x][y] = newboard[x][y], newboard[dx][dy]
                         heapq.heappush(new_q, (dist + 1, self.tupletize(newboard)))
                 
             heap = new_q
         
         return -1

class Solution:
     def slidingPuzzle(self, board):
         """
         :type board: List[List[int]]
         :rtype: int
         """
         possible_moves = {0: [1,3], 1: [0,2,4], 2: [1,5], 3: [0,4], 4: [1,3,5], 5: [2,4]}
         state = "".join([str(x) for x in board[0]]) + "".join([str(x) for x in board[1]])
         
         seen = {state: 0}
         q = [[state, state.find("0")]]
 
         while q and q[0][0] != "123450":
             cur = q.pop(0)
             for move in possible_moves[cur[1]]:
                 new_state = [int(x) for x in cur[0]]
                 new_state[cur[1]], new_state[move] = new_state[move], new_state[cur[1]]
                 new_state = "".join([str(x) for x in new_state])
                 if new_state not in seen:
                     seen[new_state] = seen[cur[0]]+1
                     q.append([new_state, move])
         return -1 if not q else seen[q[0][0]]

from functools import reduce
 from collections import deque
 class Solution:
     def slidingPuzzle(self, board):
         """
         :type board: List[List[int]]
         :rtype: int
         """
         hashtable = {}
         end, steps = "123450", None
         startstr = ''.join([str(i) for i in board[0]]) + ''.join([str(i) for i in board[1]])
         options = [[1,3],[0,2,4],[1,5],[0,4],[1,3,5],[2,4]]
         queue = deque()
         queue.append([startstr, 0])
         
         def move(currstr, moveto, currenti):
             moving = currstr[moveto]
             currstr = currstr.replace(moving, '!',)
             currstr = currstr.replace('0', moving)
             currstr = currstr.replace('!', '0')
             return currstr
         
         while (len(queue) > 0 and steps == None):
             currstr = queue.popleft()
             if currstr[0] == end:
                 steps = currstr[1]
                 break
 
             if currstr[0] not in hashtable:
                 currenti = currstr[0].find('0')
                 hashtable[currstr[0]] = True
                 possibilities = [move(currstr[0], i, currenti) for i in options[currenti]]
                 for el in possibilities:
                     queue.append([el, currstr[1] + 1])
 
         return -1 if steps == None else steps

from copy import deepcopy
 from collections import deque
 
 class Solution:
     def slidingPuzzle(self, board):
         """
         :type board: List[List[int]]
         :rtype: int
         """
         
         n, m = len(board), len(board[0])
 
         def isValid():
             def getNumberOfInversions():
                 boardInOneLine = []
                 for line in board:
                     for el in line:
                         if el != 0:
                             boardInOneLine.append(el)
 
                 inversions = 0
                 for i, l in enumerate(boardInOneLine):
                     for r in boardInOneLine[i+1:]:
                         inversions += (l > r)
                 return inversions
 
             inversions = getNumberOfInversions()
             if m%2 == 1:
                 return inversions%2 == 0
 
             def getBlankRow():
                 for i, line in enumerate(board):
                     if 0 in line:
                         return i
 
             blankRow = getBlankRow
             if inversions%2 == 0 and blankRow%2 == 1:
                 return True
             if inversions%2 == 1 and blankRow%2 == 0:
                 return True
             return False
         
         if not isValid():
             return -1
 
         def toTuple(mat):
             return tuple(tuple(line) for line in mat)
 
         def toList(mat):
             return list(list(line) for line in mat)
 
         
         def getSolution():
             sol = []
             for line in range(n):
                 sol.append([])
                 for column in range(1,m+1):
                     sol[-1].append(column+line*m)
             sol[-1][-1] = 0
             return toTuple(sol)
         
         sol = getSolution()
         h = deque([(toTuple(board),0)])
         visited = set()
         while True:
             board, count = h.popleft()
             if board == sol:
                 return count
             elif board in visited:
                 continue
             visited.add(board)
             board = toList(board)
             
             def findBlack():
                 for i, line in enumerate(board):
                     for j, el in enumerate(line):
                         if el == 0:
                             return (i,j)
 
             bx, by = findBlack()
 
             def isValidPosition(x,y):
                 return 0 <= x < n and 0 <= y < m
 
             for dx,dy in ((-1,0),(1,0),(0,-1),(0,1)):
                 if isValidPosition(dx+bx,dy+by):
                     nboard = toList(deepcopy(board))
                     nboard[bx][by], nboard[bx+dx][by+dy] = nboard[bx+dx][by+dy], nboard[bx][by]
                     h.append((toTuple(nboard),count+1))
 
 
         return -1
 


class Solution:
     def slidingPuzzle(self, board):
         """
         :type board: List[List[int]]
         :rtype: int
         """
         from collections import deque as dq
         curs = "".join(map(str,board[0])) + "".join(map(str,board[1])) 
         dist, pre = {}, {}
         dist[curs] = 0
         q = dq([curs])
         while q:
             curs = q.pop()
             if curs == "123450":
                 while curs in pre:
                     #print(curs)
                     curs = pre[curs]
                 return dist["123450"]
             #print("curs is" + curs, curs not in dist)
             ind = curs.index("0")
             if ind > 0 and ind != 3:
                 preswap = curs[:ind-1] + '0' + curs[ind-1] + curs[ind+1:]
                 #print("preswap is" + preswap)
                 if preswap not in dist:
                     dist[preswap] = dist[curs] + 1
                     pre[preswap] = curs
                     q.appendleft(preswap)
             if ind < 5 and ind != 2:
                 afterswap = curs[:ind] + curs[ind+1]  + '0' + curs[ind+2:]
                 #print("afterswap is" + afterswap)
                 if afterswap not in dist:
                     dist[afterswap] = dist[curs] + 1
                     pre[afterswap] = curs
                     q.appendleft(afterswap)
             if ind < 3:
                 downswap =  curs[:ind] + curs[ind+3] + curs[ind+1:ind+3] + '0' + curs[ind+4:]
                 #print("downswap is" + downswap)
                 if downswap not in dist:
                     dist[downswap] = dist[curs] + 1
                     pre[downswap] = curs
                     q.appendleft(downswap)
             else:
                 upswap =  curs[:ind-3] + '0' + curs[ind-2:ind] + curs[ind-3]+ curs[ind+1:]
                 #print("upwap is" + upswap)
                 if upswap not in dist:
                     dist[upswap] = dist[curs] + 1
                     pre[upswap] = curs
                     q.appendleft(upswap)
             #print(dist)
         
         return -1
                 


from collections import deque
 
 class Solution:
     def slidingPuzzle(self, b):
         seen = set()
         q = deque()
         q.append(([1,2,3,4,5,0], 5, 0))
         while q:
             u, p, m = q.popleft()
             if u == b[0] + b[1]:
                 return m
             for np in [p-1 if p != 3 else -1, p+1 if p != 2 else -1, p-3, p+3]:
                 if 0 <= np < 6:
                     v = u[:]
                     v[p], v[np] = v[np], v[p]
                     if tuple(v) not in seen:
                         seen.add(tuple(v))
                         q.append((v[:], np, m+1))
         return -1

class Solution:
     def slidingPuzzle(self, board):
         """
         :type board: List[List[int]]
         :rtype: int
         """
         q = collections.deque()
         steps = collections.defaultdict(int)
         
         start = tuple(board[0]+board[1])
         steps[start] = 0
         q.append(start)
         target = (1,2,3,4,5,0)
         
         while q:
             bd = q.popleft()
             if bd == target:
                 return steps[bd]
             ind = bd.index(0)
             i, j = ind//3, ind % 3
             for m, n in [[i-1, j], [i+1, j], [i, j-1], [i, j+1]]:
                 if 0 <= m < 2 and 0 <= n < 3:
                     move = list(bd)
                     move[ind], move[m*3+n] = move[m*3+n], move[ind]
                     new_bd = tuple(move)
                     if new_bd not in steps or steps[new_bd] > steps[bd] + 1:
                         q.append(new_bd)
                         steps[new_bd] = steps[bd] + 1
         
         return -1

from functools import reduce
 from collections import deque
 class Solution:
     def slidingPuzzle(self, board):
         """
         :type board: List[List[int]]
         :rtype: int
         """
         hashtable, queue, steps = {}, deque(), None
         startstr = ''.join([str(i) for i in board[0]]) + ''.join([str(i) for i in board[1]])
         options = [[1,3],[0,2,4],[1,5],[0,4],[1,3,5],[2,4]] # possible locations to switch for each position of 0
         queue.append([startstr, 0]) # [string to check, current num of steps]
         
         # function to switch characters in a string
         def move(string, moveto, currenti):
             moving = string[moveto]
             string = string.replace(moving, 'x',)
             string = string.replace('0', moving)
             return string.replace('x', '0')
         
         # loop through and add to queue until solution is found or all variations are examined
         while (len(queue) > 0 and steps == None):
             curr = queue.popleft()
             if curr[0] == "123450":
                 steps = curr[1]
                 break
             if curr[0] not in hashtable:
                 currenti = curr[0].find('0')
                 hashtable[curr[0]] = True
                 possibilities = [move(curr[0], i, currenti) for i in options[currenti]]
                 for el in possibilities:
                     queue.append([el, curr[1] + 1])
 
         return -1 if steps == None else steps

from collections import deque
 
 class Solution:
     def slidingPuzzle(self, board):
         """
         :type board: List[List[int]]
         :rtype: int
         """
         t = tuple(board[0]), tuple(board[1])
         v,q = set([t]), deque([(t, 0)])
         
         def addNeighbor(i, j, a, b, steps):
             if 0 <= a < 2 and 0 <= b < 3:
                 board[i][j], board[a][b] = board[a][b], board[i][j]
                 t = tuple(board[0]), tuple(board[1])
                 if t not in v:
                     v.add(t)
                     q.append((t, steps + 1))
                 board[i][j], board[a][b] = board[a][b], board[i][j]
         
         while q:
             t, steps = q.popleft()
             if t == ((1, 2, 3), (4, 5, 0)):
                 return steps
             
             board[0], board[1] = list(t[0]), list(t[1])
             for i in range(2):
                 for j in range(3):
                     if board[i][j] == 0:
                         addNeighbor(i, j, i - 1, j, steps)
                         addNeighbor(i, j, i + 1, j, steps)
                         addNeighbor(i, j, i, j - 1, steps)
                         addNeighbor(i, j, i, j + 1, steps)
         
         return -1

class Solution:
     def __init__(self):
         self.win = [[1,2,3],[4,5,0]]
         self.lose = [[[1,2,3],[5,4,0]],[[2,1,3],[4,5,0]],[[1,3,2],[4,5,0]],
                     [[3,0,1],[4,2,5]],[[4,2,3],[1,5,0]],[[1,5,3],[4,2,0]]]
         
         
     def slidingPuzzle(self, board):
         """
         :type board: List[List[int]]
         :rtype: int
         """
         s = 0
         if board == self.win:
             return 0
         to = [board]
         path = [board]
         while True:
             s += 1
             t = []
             for x in to:
                 tmp = self.move(x)
                 for z in tmp:
                     if z not in path:
                         path.append(z)
                         t.append(z)
             for y in t:
                 if (y == self.win):
                     return s
                 else:
                     for z in self.lose:
                         if z == y:
                             return -1
             to = t    
         return -1
     
     def same(self, x, y):
         for i in range(2):
             for j in range(3):
                 if x[i][j] != y[i][j]:
                     return False
         return True
     
     def copy(self, x):
         r = []
         for y in x:
             r.append(y.copy())
         return r
         
     def move(self, bd):
         p = self.find(bd)
         r = []
         low = p[0] > 0
         le = p[1] == 0
         re = p[1] == 2
         if not le:
             to = self.copy(bd)
             to[p[0]][p[1]] = bd[p[0]][p[1]-1]
             to[p[0]][p[1]-1] = 0
             r.append(to)
         if not re:
             to = self.copy(bd)
             to[p[0]][p[1]] = bd[p[0]][p[1]+1]
             to[p[0]][p[1]+1] = 0
             r.append(to)
         if low:
             to = self.copy(bd)
             to[p[0]][p[1]] = bd[p[0]-1][p[1]]
             to[p[0]-1][p[1]] = 0
             r.append(to)
         else:
             to = self.copy(bd)
             to[p[0]][p[1]] = bd[p[0]+1][p[1]]
             to[p[0]+1][p[1]] = 0
             r.append(to)        
         return r
         
     def find(self, bd):
         for i, x in enumerate(bd):
             if 0 in x:
                 return (i, x.index(0))

class Solution:
     def __init__(self):
       self.GOAL_STATE = [1, 2, 3, 4, 5, 0]
   
     def slidingPuzzle(self, board):
       """
       :type board: List[List[int]]
       :rtype: int
       """
       from itertools import chain
       seen = set()
       
       from collections import deque
       q = deque()
       q.append((list(chain.from_iterable(board)), 0))
       
       while q:
         state, dist = q.popleft()
         seen.add(tuple(state))
         
         if state == self.GOAL_STATE:
           return dist
         
         for nextState in self.nextStates(state):
           if tuple(nextState) not in seen:
             q.append((nextState, dist + 1))
       
       return -1
       
     def swap(self, state, i, j):
       temp = state[i]
       state[i] = state[j]
       state[j] = temp
       
     def getNeighbors(self, index):
       neighbors = {0:[1,3], 1:[0, 4, 2], 2: [1,5], 3:[0,4], 4: [3, 1, 5], 5: [4, 2]}
       return neighbors[index]
       
     def nextStates(self, state):
       states = []
       zeroIndex = state.index(0)
       
       for nei in self.getNeighbors(zeroIndex):
         nextState = list(state)
         self.swap(nextState, nei, zeroIndex)
         states.append(nextState)
       return states
 
         


class Solution:
     def slidingPuzzle(self, board):
         """
         :type board: List[List[int]]
         :rtype: int
         """
         step=0
         board=tuple(map(tuple,board))
         q=[board]
         memo=set([board])
         while q:
             q0=[]
             for b in q:
                 if b==((1,2,3),(4,5,0)):
                     return step
                 for x in range(2):
                     for y in range(3):
                         if b[x][y]:
                             continue
                         for dx,dy in zip((1,0,-1,0),(0,1,0,-1)):
                             nx,ny=x+dx,y+dy
                             if 0<=nx<2 and 0<=ny<3:
                                 nb=list(map(list,b))
                                 nb[x][y],nb[nx][ny]=nb[nx][ny],nb[x][y]
                                 nb=tuple(map(tuple,nb))
                                 if nb not in memo:
                                     memo.add(nb)
                                     q0.append(nb)
             q=q0
             step+=1
         return -1 #注意最后一步 返回的是-1
                                 
                             


class Solution:
     def slidingPuzzle(self, board):
         """
         :type board: List[List[int]]
         :rtype: int
         """
         step=0
         board=tuple(map(tuple,board))
         q=[board]
         memo=set([board])
         while q:
             q0=[]
             for b in q:
                 if b==((1,2,3),(4,5,0)):
                     return step
                 for x in range(2):
                     for y in range(3):
                         if b[x][y]:
                             continue
                         for dx,dy in zip((1,0,-1,0),(0,1,0,-1)):
                             nx,ny=x+dx,y+dy
                             if 0<=nx<2 and 0<=ny<3:
                                 nb=list(map(list,b))
                                 nb[x][y],nb[nx][ny]=nb[nx][ny],nb[x][y]
                                 nb=tuple(map(tuple,nb))
                                 if nb not in memo:
                                     memo.add(nb)
                                     q0.append(nb)
             q=q0
             step+=1
         return -1