Here is my python solution. I decided to use the List of lists instead of converting it to a tuple. For the set, I had a stringify_matrix function.
from typing import List
from collections import deque
def get_next_possible_swaps(curr_pos: List[List[int]], r: int, c: int):
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
possible_swaps = []
for direction in directions:
new_r = r + direction[0]
new_c = c + direction[1]
# if you try to simply set a temporary variable like below:
# new_pos = curr_pos
# then, BFS will not work you must get a new copy of curr_pos and
# assign it to new_pos like so
# new_pos = list(list(line) for line in curr_pos)
new_pos = list(list(line) for line in curr_pos)
if 0 <= new_r < len(curr_pos) and 0 <= new_c < len(curr_pos[0]):
new_pos[r][c], new_pos[new_r][new_c] = new_pos[new_r][new_c], new_pos[r][c]
possible_swaps.append(new_pos)
return possible_swaps
Time complexity O(m + n)
def stringify_matrix(matrix: List[List[int]]) → str:
ordered_nums = []
for r in range(len(matrix)):
for c in range(len(matrix[0])):
ordered_nums.append(str(matrix[r][c]))
return “”.join(ordered_nums)
Time complexity O(n!)
def num_steps(init_pos: List[List[int]]) → int:
target = [[1,2,3],[4,5,0]]
queue = deque([init_pos])
visited = set([stringify_matrix(init_pos)])
moves_required = 0
while len(queue) > 0:
n = len(queue)
for _ in range(n):
curr_pos = queue.popleft()
if curr_pos == target:
return moves_required
for r in range(len(curr_pos)):
for c in range(len(curr_pos[0])):
if curr_pos[r][c] == 0:
for swap in get_next_possible_swaps(curr_pos, r, c):
stringified_swap = stringify_matrix(swap)
if stringified_swap not in visited:
queue.append(swap)
visited.add(stringified_swap)
moves_required += 1
return -1