Hard

题目描述

在一个 2 x 3 的板上有 5 个方块，分别标记为 1 到 5，还有一个空格用 0 表示。一次移动定义为选择 0 与一个相邻的数字（上下左右）进行交换。

当且仅当板子状态为 [[1,2,3],[4,5,0]] 时，谜题解开。

给你一个谜题的初始状态 board ，返回最少的移动次数使得状态到达已解状态。如果不可能达到已解状态，则返回 -1。

示例 1：

输入：board = [[1,2,3],[4,0,5]]
输出：1
解释：交换 0 和 5 ，一步完成

示例 2：

输入：board = [[1,2,3],[5,4,0]]
输出：-1
解释：没有办法完成谜题

示例 3：

输入：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]]

提示：

  • board.length == 2
  • board[i].length == 3
  • 0 <= board[i][j] <= 5
  • board[i][j] 中每个值都不同

解题思路

这是一个经典的状态空间搜索问题，需要找到从初始状态到目标状态的最短路径。

核心思路：

  1. 状态表示：将2x3的二维矩阵压缩为字符串表示状态，便于哈希和比较
  2. BFS最短路径：使用广度优先搜索保证找到最少的移动次数
  3. 状态转移：对于每个状态，找到0的位置，尝试与相邻位置交换生成新状态

实现要点：

  • 将二维坐标映射为一维：位置(i,j)对应索引i*3+j
  • 预定义邻接关系：每个位置可以移动到的相邻位置
  • 使用队列进行BFS，记录访问过的状态避免重复
  • 目标状态是"123450"

邻接关系分析：

位置: 0 1 2
     3 4 5
  • 位置0可以移动到1,3
  • 位置1可以移动到0,2,4
  • 位置2可以移动到1,5
  • 位置3可以移动到0,4
  • 位置4可以移动到1,3,5
  • 位置5可以移动到2,4

时间复杂度主要取决于状态空间大小，对于2x3的板子，理论上最多有6!种排列。

代码实现

class Solution {
public:
    int slidingPuzzle(vector<vector<int>>& board) {
        string start = "";
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 3; j++) {
                start += to_string(board[i][j]);
            }
        }
        
        string target = "123450";
        if (start == target) return 0;
        
        vector<vector<int>> neighbors = {
            {1, 3},
            {0, 2, 4},
            {1, 5},
            {0, 4},
            {1, 3, 5},
            {2, 4}
        };
        
        queue<pair<string, int>> q;
        unordered_set<string> visited;
        
        q.push({start, 0});
        visited.insert(start);
        
        while (!q.empty()) {
            auto [state, moves] = q.front();
            q.pop();
            
            int zeroPos = state.find('0');
            
            for (int nextPos : neighbors[zeroPos]) {
                string nextState = state;
                swap(nextState[zeroPos], nextState[nextPos]);
                
                if (nextState == target) {
                    return moves + 1;
                }
                
                if (visited.find(nextState) == visited.end()) {
                    visited.insert(nextState);
                    q.push({nextState, moves + 1});
                }
            }
        }
        
        return -1;
    }
};

class Solution:
    def slidingPuzzle(self, board: List[List[int]]) -> int:
        start = "".join(str(board[i][j]) for i in range(2) for j in range(3))
        target = "123450"
        
        if start == target:
            return 0
        
        neighbors = {
            0: [1, 3],
            1: [0, 2, 4],
            2: [1, 5],
            3: [0, 4],
            4: [1, 3, 5],
            5: [2, 4]
        }
        
        queue = collections.deque([(start, 0)])
        visited = {start}
        
        while queue:
            state, moves = queue.popleft()
            zero_pos = state.index('0')
            
            for next_pos in neighbors[zero_pos]:
                next_state = list(state)
                next_state[zero_pos], next_state[next_pos] = next_state[next_pos], next_state[zero_pos]
                next_state = "".join(next_state)
                
                if next_state == target:
                    return moves + 1
                
                if next_state not in visited:
                    visited.add(next_state)
                    queue.append((next_state, moves + 1))
        
        return -1

public class Solution {
    public int SlidingPuzzle(int[][] board) {
        string start = "";
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 3; j++) {
                start += board[i][j].ToString();
            }
        }
        
        string target = "123450";
        if (start == target) return 0;
        
        int[][] neighbors = new int[][] {
            new int[] {1, 3},
            new int[] {0, 2, 4},
            new int[] {1, 5},
            new int[] {0, 4},
            new int[] {1, 3, 5},
            new int[] {2, 4}
        };
        
        Queue<(string state, int moves)> queue = new Queue<(string, int)>();
        HashSet<string> visited = new HashSet<string>();
        
        queue.Enqueue((start, 0));
        visited.Add(start);
        
        while (queue.Count > 0) {
            var (state, moves) = queue.Dequeue();
            int zeroPos = state.IndexOf('0');
            
            foreach (int nextPos in neighbors[zeroPos]) {
                char[] nextStateArray = state.ToCharArray();
                (nextStateArray[zeroPos], nextStateArray[nextPos]) = (nextStateArray[nextPos], nextStateArray[zeroPos]);
                string nextState = new string(nextStateArray);
                
                if (nextState == target) {
                    return moves + 1;
                }
                
                if (!visited.Contains(nextState)) {
                    visited.Add(nextState);
                    queue.Enqueue((nextState, moves + 1));
                }
            }
        }
        
        return -1;
    }
}

/**
 * @param {number[][]} board
 * @return {number}
 */
var slidingPuzzle = function(board) {
    const target = "123450";
    const start = board[0].join("") + board[1].join("");
    
    if (start === target) return 0;
    
    const neighbors = {
        0: [1, 3],
        1: [0, 2, 4],
        2: [1, 5],
        3: [0, 4],
        4: [1, 3, 5],
        5: [2, 4]
    };
    
    const queue = [start];
    const visited = new Set([start]);
    let moves = 0;
    
    while (queue.length > 0) {
        const size = queue.length;
        moves++;
        
        for (let i = 0; i < size; i++) {
            const current = queue.shift();
            const zeroIndex = current.indexOf('0');
            
            for (const neighbor of neighbors[zeroIndex]) {
                const arr = current.split('');
                [arr[zeroIndex], arr[neighbor]] = [arr[neighbor], arr[zeroIndex]];
                const next = arr.join('');
                
                if (next === target) return moves;
                
                if (!visited.has(next)) {
                    visited.add(next);
                    queue.push(next);
                }
            }
        }
    }
    
    return -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(6!) = O(720)
空间复杂度O(6!) = O(720)

说明：

  • 时间复杂度：最坏情况下需要遍历所有可能的状态，2x3板子最多有6!种不同排列
  • 空间复杂度：需要存储访问过的状态和队列中的状态，最多6!个状态