LeetCode773. 滑动谜题

题目

在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示。一次 移动 定义为选择 0 与一个相邻的数字（上下左右）进行交换.

最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。

给出一个谜板的初始状态 board ，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。

示例 1：

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

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

题解

关键是把二维的数组转成一维。
0的上下左右位置可以直接算出是一维的哪个位置

class Solution {
public int slidingPuzzle(int[][] board) {
    int m = 2, n = 3;
    StringBuilder sb = new StringBuilder();
    String target = "123450";
    // 将 2x3 的数组转化成字符串作为 BFS 的起点
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            sb.append(board[i][j]);
        }
    }
    String start = sb.toString();

    // 记录一维字符串的相邻索引
    int[][] neighbor = new int[][]{
            {1, 3},
            {0, 4, 2},
            {1, 5},
            {0, 4},
            {3, 1, 5},
            {4, 2}
    };

    /******* BFS 算法框架开始 *******/
    Queue<String> q = new LinkedList<>();
    HashSet<String> visited = new HashSet<>();
    // 从起点开始 BFS 搜索
    q.offer(start);
    visited.add(start);

    int step = 0;
    while (!q.isEmpty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            String cur = q.poll();
            // 判断是否达到目标局面
            if (target.equals(cur)) {
                return step;
            }
            // 找到数字 0 的索引
            int idx = 0;
            for (; cur.charAt(idx) != '0'; idx++) ;
            // 将数字 0 和相邻的数字交换位置
            for (int adj : neighbor[idx]) {
                String new_board = swap(cur.toCharArray(), adj, idx);
                // 防止走回头路
                if (!visited.contains(new_board)) {
                    q.offer(new_board);
                    visited.add(new_board);
                }
            }
        }
        step++;
    }
    /******* BFS 算法框架结束 *******/
    return -1;
}

private String swap(char[] chars, int i, int j) {
    char temp = chars[i];
    chars[i] = chars[j];
    chars[j] = temp;
    return new String(chars);
}

}