滑动谜题(Leetcode 773)

题目分析

   这是一个困难的题目，不要被它吓倒了，这个题目和昨天的打开转盘锁类似，只不过本题的状态改变和状态的表示复杂一些

广度优先搜索

本题的起始状态为board，终止状态为[[1, 2, 3], [4, 5, 0]]，因此同样可以使用双向BFS进行求解。
因为0代表空缺位置，因此只有0附近的元素可以进行移动，我们使用长度为6字符串表示元素的状态，分别代表board的6个数字。
当0出现在board[0][0]时，可以和board[0][1]、board[1][0]互换位置，因此str[0]可以和str[1]、str[3]交换
当0出现在board[0][1]时，可以和board[0][0]、board[0][2]、board[1][1]互换位置，因此str[1]可以和str[0]、str[2]、str[4]交换
当0出现在board[0][2]时，可以和board[0][1]、board[1][2]互换位置，因此str[2]可以和str[1]、str[5]交换
当0出现在board[1][0]时，可以和board[0][0]、board[1][1]互换位置，因此str[3]可以和str[0]、str[4]交换
当0出现在board[1][1]时，可以和board[0][1]、board[1][0]、board[1][2]互换位置，因此str[1]可以和str[1]、str[3]、str[5]交换
当0出现在board[1][2]时，可以和board[0][2]、board[1][1]互换位置，因此str[5]可以和str[2]、str[4]交换

用一个长度为6二维数组dir，每一个元素代表可以交换的位置列表，如dir[0] = {1， 3}代表str[0]可以和str[1]和str[3]进行交换，这样可以快速获得下一个状态的表示。

算法的**时间复杂度为$O((mn)!)$，空间复杂度为$O((mn)! \times mn)$**，其中m和n分别代表行数和列数，$(mn)!$表示所有可能的状态，即本题0-5六个数字的全排列

下面是Java语言的题解

class Solution {
    public int slidingPuzzle(int[][] board) {
        String target = "123450";
        String begin = Integer.toString(board[0][0]) + board[0][1] + board[0][2] + board[1][0] + board[1][1] + board[1][2];
        if (target.equals(begin)) { return 0; }
        int[][] dir = new int[][] {{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}};
        LinkedList<String> beginQueue = new LinkedList<>();
        beginQueue.add(begin);
        LinkedList<String> endQueue = new LinkedList<>();
        endQueue.add(target);
        HashSet<String> beginVisited = new HashSet<>();
        beginVisited.add(begin);
        HashSet<String> endVisited = new HashSet<>();
        endVisited.add(target);
        int res = 0;
        while (true) {
            res++;
            int beginSize = beginQueue.size();
            while (beginSize-- > 0) {
                String cur = beginQueue.removeFirst();
                int zeroPos = cur.indexOf('0');
                for (int p : dir[zeroPos]) {
                    StringBuilder stringBuilder = new StringBuilder(cur);
                    stringBuilder.setCharAt(zeroPos, cur.charAt(p));
                    stringBuilder.setCharAt(p, '0');
                    String nextString = stringBuilder.toString();
                    if (!beginVisited.contains(nextString)) {
                        if (endVisited.contains(nextString)) { return res; }
                        beginVisited.add(nextString);
                        beginQueue.add(nextString);
                    }
                }
            }
            if (beginQueue.isEmpty()) { return -1; }

            res++;
            int endSize = endQueue.size();
            while (endSize-- > 0) {
                String cur = endQueue.removeFirst();
                int zeroPos = cur.indexOf('0');
                for (int p : dir[zeroPos]) {
                    StringBuilder stringBuilder = new StringBuilder(cur);
                    stringBuilder.setCharAt(zeroPos, cur.charAt(p));
                    stringBuilder.setCharAt(p, '0');
                    String nextString = stringBuilder.toString();
                    if (!endVisited.contains(nextString)) {
                        if (beginVisited.contains(nextString)) { return res; }
                        endVisited.add(nextString);
                        endQueue.add(nextString);
                    }
                }
            }
            if (endQueue.isEmpty()) { return -1; }
        }
    }
}

下面是Kotlin语言的题解

class Solution {
    fun slidingPuzzle(board: Array<IntArray>): Int {
        val target = "123450"
        val begin = board[0][0].toString() + board[0][1].toString() + board[0][2].toString() + board[1][0].toString() + board[1][1].toString() + board[1][2].toString()
        if (target == begin) { return 0 }
        val dir = arrayOf(intArrayOf(1, 3), intArrayOf(0, 2, 4), intArrayOf(1, 5), intArrayOf(0, 4), intArrayOf(1, 3, 5), intArrayOf(2, 4))
        val beginQueue = LinkedList<String>()
        beginQueue.add(begin)
        val endQueue = LinkedList<String>()
        endQueue.add(target)
        val beginVisited = HashSet<String>()
        beginVisited.add(begin)
        val endVisited = HashSet<String>()
        endVisited.add(target)
        var res = 0
        while (true) {
            res++
            var beginSize = beginQueue.size
            while (beginSize-- > 0) {
                val cur = beginQueue.removeFirst()
                val zeroPos = cur.indexOf('0')
                for (p in dir[zeroPos]) {
                    val stringBulider = StringBuilder(cur)
                    stringBulider.setCharAt(zeroPos, cur[p])
                    stringBulider.setCharAt(p, '0')
                    val nextString = stringBulider.toString()
                    if (!beginVisited.contains(nextString)) {
                        if (endVisited.contains(nextString)) { return res }
                        beginQueue.add(nextString)
                        beginVisited.add(nextString)
                    }
                }
            }
            if (beginQueue.isEmpty()) { return -1 }

            res++
            var endSize = endQueue.size
            while (endSize-- > 0) {
                val cur = endQueue.removeFirst()
                val zeroPos = cur.indexOf('0')
                for (p in dir[zeroPos]) {
                    val stringBulider = StringBuilder(cur)
                    stringBulider.setCharAt(zeroPos, cur[p])
                    stringBulider.setCharAt(p, '0')
                    val nextString = stringBulider.toString()
                    if (!endVisited.contains(nextString)) {
                        if (beginVisited.contains(nextString)) { return res }
                        endQueue.add(nextString)
                        endVisited.add(nextString)
                    }
                }
            }
            if (endQueue.isEmpty()) { return -1 }
        }
    }
}

刷题总结

  最近几天是BFS/DFS的专项训练，这是必须要掌握的算法之一，希望小伙伴要认真对待。