Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/773.html
773. Sliding Puzzle
Level
Hard
Description
On a 2x3 board, there are 5 tiles represented by the integers 1 through 5, and an empty square represented by 0.
A move consists of choosing 0 and a 4-directionally adjacent number and swapping it.
The state of the board is solved if and only if the board is [[1,2,3],[4,5,0]].
Given a puzzle board, return the least number of moves required so that the state of the board is solved. If it is impossible for the state of the board to be solved, return -1.
Examples:
Input: board = [[1,2,3],[4,0,5]]
Output: 1
Explanation: Swap the 0 and the 5 in one move.
Input: board = [[1,2,3],[5,4,0]]
Output: -1
Explanation: No number of moves will make the board solved.
Input: board = [[4,1,2],[5,0,3]]
Output: 5
Explanation: 5 is the smallest number of moves that solves the board.
An example path:
After move 0: [[4,1,2],[5,0,3]]
After move 1: [[4,1,2],[0,5,3]]
After move 2: [[0,1,2],[4,5,3]]
After move 3: [[1,0,2],[4,5,3]]
After move 4: [[1,2,0],[4,5,3]]
After move 5: [[1,2,3],[4,5,0]]
Input: board = [[3,2,4],[1,5,0]]
Output: 14
Note:
boardwill be a 2 x 3 array as described above.board[i][j]will be a permutation of[0, 1, 2, 3, 4, 5].
Solution
To find the least number of moves required to reach the state that the board is solved, use breadth first search. First find the position of the empty square 0. Starting from the initial board, try all four directions and in each direction, swap 0 with its adjacent element if there is an adjacent element in the direction. If the new state is solved, then return the number of moves. Otherwise, if the new state has not been visited before, add the new state to the queue for further search, and update the number of moves. If all possible states are tried and the board cannot be solved, return -1.
To check whether a state has been visited, convert the 2D array into a string and use a set to store the converted strings. If the set contains the converted string, then the state has been visited. Otherwise, the state has not been visited.
-
class Solution { public int slidingPuzzle(int[][] board) { if (isSolved(board)) return 0; Set<String> visitedSet = new HashSet<String>(); visitedSet.add(arrayToString(board)); int zeroRow = -1, zeroColumn = -1; outer: for (int i = 0; i < 2; i++) { for (int j = 0; j < 3; j++) { if (board[i][j] == 0) { zeroRow = i; zeroColumn = j; break outer; } } } int moves = 0; int[][] directions = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; Queue<int[][]> stateQueue = new LinkedList<int[][]>(); Queue<int[]> zeroQueue = new LinkedList<int[]>(); stateQueue.offer(board); zeroQueue.offer(new int[]{zeroRow, zeroColumn}); while (!stateQueue.isEmpty()) { moves++; int size = stateQueue.size(); for (int i = 0; i < size; i++) { int[][] prevState = stateQueue.poll(); int[] zero = zeroQueue.poll(); int curRow = zero[0], curColumn = zero[1]; for (int[] direction : directions) { int newRow = curRow + direction[0], newColumn = curColumn + direction[1]; if (newRow >= 0 && newRow < 2 && newColumn >= 0 && newColumn < 3) { int[][] newState = new int[2][3]; for (int j = 0; j < 2; j++) { for (int k = 0; k < 3; k++) newState[j][k] = prevState[j][k]; } newState[curRow][curColumn] = prevState[newRow][newColumn]; newState[newRow][newColumn] = prevState[curRow][curColumn]; if (isSolved(newState)) return moves; else { String boardStr = arrayToString(newState); if (visitedSet.add(boardStr)) { stateQueue.offer(newState); zeroQueue.offer(new int[]{newRow, newColumn}); } } } } } } return -1; } public String arrayToString(int[][] board) { return "[" + Arrays.toString(board[0]) + ", " + Arrays.toString(board[1]) + "]"; } public boolean isSolved(int[][] board) { for (int i = 0; i < 2; i++) { if (board[0][i] != i + 1 || board[1][i] != i + 4) return false; } if (board[0][2] != 3 || board[1][2] != 0) return false; return true; } } -
// OJ: https://leetcode.com/problems/sliding-puzzle/ // Time: O(1) // Space: O(1) class Solution { public: int slidingPuzzle(vector<vector<int>>& A) { string target = "123450", start; int ans = 0; vector<vector<int>> neighbors = { {1,3},{0,2,4},{1,5},{0,4},{1,3,5},{2,4} }; for (int i = 0; i < 2; ++i) { for (int j = 0; j < 3; ++j) start += '0' + A[i][j]; } if (target == start) return 0; unordered_set<string> seen; seen.insert(start); queue<string> q; q.push(start); while (q.size()) { int cnt = q.size(); ++ans; while (cnt--) { auto B = q.front(); q.pop(); int from = 0; for (int i = 0; i < 6; ++i) { if (B[i] == '0') { from = i; break; } } for (auto &to : neighbors[from]) { swap(B[from], B[to]); if (B == target) return ans; if (seen.count(B) == 0) { seen.insert(B); q.push(B); } swap(B[from], B[to]); } } } return -1; } }; -
class Solution: def slidingPuzzle(self, board: List[List[int]]) -> int: m, n = 2, 3 seq = [] start, end = '', '123450' for i in range(m): for j in range(n): if board[i][j] != 0: seq.append(board[i][j]) start += str(board[i][j]) def check(seq): n = len(seq) cnt = sum(seq[i] > seq[j] for i in range(n) for j in range(i, n)) return cnt % 2 == 0 def f(s): ans = 0 for i in range(m * n): if s[i] != '0': num = ord(s[i]) - ord('1') ans += abs(i // n - num // n) + abs(i % n - num % n) return ans if not check(seq): return -1 q = [(f(start), start)] dist = {start: 0} while q: _, state = heappop(q) if state == end: return dist[state] p1 = state.index('0') i, j = p1 // n, p1 % n s = list(state) for a, b in [[0, -1], [0, 1], [1, 0], [-1, 0]]: x, y = i + a, j + b if 0 <= x < m and 0 <= y < n: p2 = x * n + y s[p1], s[p2] = s[p2], s[p1] next = ''.join(s) s[p1], s[p2] = s[p2], s[p1] if next not in dist or dist[next] > dist[state] + 1: dist[next] = dist[state] + 1 heappush(q, (dist[next] + f(next), next)) return -1 ############ class Solution(object): def slidingPuzzle(self, board): """ :type board: List[List[int]] :rtype: int """ goal = "123450" start = self.board2str(board) bfs = collections.deque() bfs.append((start, 0)) visited = set() visited.add(start) dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)] while bfs: path, step = bfs.popleft() if path == goal: return step p = path.index("0") x, y = p / 3, p % 3 path = list(path) for dir in dirs: tx, ty = x + dir[0], y + dir[1] if tx < 0 or tx >= 2 or ty < 0 or ty >= 3: continue path[tx * 3 + ty], path[x * 3 + y] = path[x * 3 + y], path[tx * 3 + ty] pathStr = "".join(path) if pathStr not in visited: bfs.append((pathStr, step + 1)) visited.add(pathStr) path[tx * 3 + ty], path[x * 3 + y] = path[x * 3 + y], path[tx * 3 + ty] return -1 def board2str(self, board): bstr = "" for i in range(2): for j in range(3): bstr += str(board[i][j]) return bstr