九章算法 | 字节跳动面试题：滑动拼图 II

[hakunamatata11]

描述

在一个 3x3 的网格中，放着编号 1 到 8 的 8 块板，以及一块编号为 0 的空格。

一次移动可以把空格 0 与上下左右四邻接之一的板子交换。

给定初始和目标的板子排布，返回到目标排布最少的移动次数。

如果不能从初始排布移动到目标排布，返回-1.

在线评测地址

样例 1

输入:
[
 [2,8,3],
 [1,0,4],
 [7,6,5]
]
[
 [1,2,3],
 [8,0,4],
 [7,6,5]
]
输出:
4

解释:
[                 [
 [2,8,3],          [2,0,3],
 [1,0,4],   -->    [1,8,4],
 [7,6,5]           [7,6,5]
]                 ]

[                 [
 [2,0,3],          [0,2,3],
 [1,8,4],   -->    [1,8,4],
 [7,6,5]           [7,6,5]
]                 ]

[                 [
 [0,2,3],          [1,2,3],
 [1,8,4],   -->    [0,8,4],
 [7,6,5]           [7,6,5]
]                 ]

[                 [
 [1,2,3],          [1,2,3],
 [0,8,4],   -->    [8,0,4],
 [7,6,5]           [7,6,5]
]                 ]

样例 2

输入:
[[2,3,8],[7,0,5],[1,6,4]]
[[1,2,3],[8,0,4],[7,6,5]]
输出:
-1

使用单向 BFS 算法

public class Solution {
    /**
     * @param init_state: the initial state of chessboard
     * @param final_state: the final state of chessboard
     * @return: return an integer, denote the number of minimum moving
     */
    public int minMoveStep(int[][] init_state, int[][] final_state) {
        String source = matrixToString(init_state);
        String target = matrixToString(final_state);

        Queue<String> queue = new LinkedList<>();
        Map<String, Integer> distance = new HashMap<>();

        queue.offer(source);
        distance.put(source, 0);

        while (!queue.isEmpty()) {
            String curt = queue.poll();
            if (curt.equals(target)) {
                return distance.get(curt);
            }

            for (String next : getNext(curt)) {
                if (distance.containsKey(next)) {
                    continue;
                }
                queue.offer(next);
                distance.put(next, distance.get(curt) + 1);
            }
        }

        return -1;
    }

    public String matrixToString(int[][] state) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                sb.append(state[i][j]);
            }
        }
        return sb.toString();
    }

    public List<String> getNext(String state) {
        List<String> states = new ArrayList<>();
        int[] dx = {0, 1, -1, 0};
        int[] dy = {1, 0, 0, -1};

        int zeroIndex = state.indexOf('0');
        int x = zeroIndex / 3;
        int y = zeroIndex % 3;

        for (int i = 0; i < 4; i++) {
            int x_ = x + dx[i];
            int y_ = y + dy[i];
            if (x_ < 0 || x_ >= 3 || y_ < 0 || y_ >= 3) {
                continue;
            }

            char[] chars = state.toCharArray();
            chars[x * 3 + y] = chars[x_ * 3 + y_];
            chars[x_ * 3 + y_] = '0';
            states.add(new String(chars));
        }

        return states;
    }
}

使用双向 BFS 算法。可以把这份代码当模板背诵。

public class Solution {
    /**
     * @param init_state: the initial state of chessboard
     * @param final_state: the final state of chessboard
     * @return: return an integer, denote the number of minimum moving
     */
    public int minMoveStep(int[][] init_state, int[][] final_state) {
        String source = matrixToString(init_state);
        String target = matrixToString(final_state);

        if (source.equals(target)) {
            return 0;
        }

        Queue<String> forwardQueue = new ArrayDeque<>();
        Set<String> forwardSet = new HashSet<>();
        forwardQueue.offer(source);
        forwardSet.add(source);

        Queue<String> backwardQueue = new ArrayDeque<>();
        Set<String> backwardSet = new HashSet<>();
        backwardQueue.offer(target);
        backwardSet.add(target);

        int steps = 0;
        while (!forwardQueue.isEmpty() && !backwardQueue.isEmpty()) {
            steps++;
            if (extendQueue(forwardQueue, forwardSet, backwardSet)) {
                return steps;
            }

            steps++;
            if (extendQueue(backwardQueue, backwardSet, forwardSet)) {
                return steps;
            }
        }

        return -1;
    }

    private boolean extendQueue(Queue<String> queue,
                                Set<String> set,
                                Set<String> targetSet) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            String curt = queue.poll();
            for (String next : getNext(curt)) {
                if (set.contains(next)) {
                    continue;
                }
                if (targetSet.contains(next)) {
                    return true;
                }
                queue.offer(next);
                set.add(next);
            }
        }
        return false;
    }

    public String matrixToString(int[][] state) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                sb.append(state[i][j]);
            }
        }
        return sb.toString();
    }

    public List<String> getNext(String state) {
        List<String> states = new ArrayList<>();
        int[] dx = {0, 1, -1, 0};
        int[] dy = {1, 0, 0, -1};

        int zeroIndex = state.indexOf('0');
        int x = zeroIndex / 3;
        int y = zeroIndex % 3;

        for (int i = 0; i < 4; i++) {
            int x_ = x + dx[i];
            int y_ = y + dy[i];
            if (x_ < 0 || x_ >= 3 || y_ < 0 || y_ >= 3) {
                continue;
            }

            char[] chars = state.toCharArray();
            chars[x * 3 + y] = chars[x_ * 3 + y_];
            chars[x_ * 3 + y_] = '0';
            states.add(new String(chars));
        }

        return states;
    }
}

戳我学习更多题解 戳我免费试听算法课程前三章