• leetcode难度:困难773. 滑动谜题


    在一个 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
    解释:没有办法完成谜板
    示例 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]]

    解题思路:使用BFS广度搜索,把二维数组换成字符串,判断是否访问

    class Solution {
        public int slidingPuzzle(int[][] board) {
            //当前交换次数
            int lev = 0;
            //转换成字符串
            String s = toString(board);
            //BFS队列
            Queue queue = new ArrayDeque<>();
            queue.offer(s);
            //访问过的字符串
            Set set = new HashSet<>();
            Map map = new HashMap<>();
            while (!queue.isEmpty()) {
                String cur = queue.poll();
                int[][] arr = toArr(cur, board.length, board[0].length);
                //是否结束
                if (isEnd(arr)) {
                    return lev;
                }
                set.add(cur);
                int zeroRow = -1;
                int zeroCol = -1;
                //寻找0的位置
                for (int i = 0; i < arr.length; i++) {
                    for (int j = 0; j < arr[i].length; j++) {
                        if (arr[i][j] == 0) {
                            zeroRow = i;
                            zeroCol = j;
                            break;
                        }
                    }
                }
                //上
                if (zeroRow > 0) {
                    int[][] board1 = clone(arr);
                    int tmp = board1[zeroRow - 1][zeroCol];
                    board1[zeroRow - 1][zeroCol] = 0;
                    board1[zeroRow][zeroCol] = tmp;
                    String ss = toString(board1);
    
                    if (!set.contains(ss)) {
                        queue.offer(ss);
                        map.put(ss, lev + 1);
                    }
    
                }
                //左
                if (zeroCol > 0) {
                    int[][] board1 = clone(arr);
                    int tmp = board1[zeroRow][zeroCol - 1];
                    board1[zeroRow][zeroCol - 1] = 0;
                    board1[zeroRow][zeroCol] = tmp;
                    String ss = toString(board1);
                    if (!set.contains(ss)) {
                        queue.offer(ss);
                        map.put(ss, lev + 1);
                    }
                }
                //右
                if (zeroCol < 2) {
                    int[][] board1 = clone(arr);
                    int tmp = board1[zeroRow][zeroCol + 1];
                    board1[zeroRow][zeroCol + 1] = 0;
                    board1[zeroRow][zeroCol] = tmp;
                    String ss = toString(board1);
                    if (!set.contains(ss)) {
                        queue.offer(ss);
                        map.put(ss, lev + 1);
                    }
                }
                //下
                if (zeroRow < 1) {
                    int[][] board1 = clone(arr);
                    int tmp = board1[zeroRow + 1][zeroCol];
                    board1[zeroRow + 1][zeroCol] = 0;
                    board1[zeroRow][zeroCol] = tmp;
                    String ss = toString(board1);
                    if (!set.contains(ss)) {
                        queue.offer(ss);
                        map.put(ss, lev + 1);
                    }
                }
    
                String next = queue.peek();
                if ((next != null && map.get(next) != lev) ||  next == null) {
                    lev++;
                }
            }
            return -1;
        }
    
        public int[][] clone(int[][] arr) {
            int[][] r = new int[arr.length][arr[0].length];
            for (int i = 0; i < arr.length; i++) {
                for (int j = 0; j < arr[i].length; j++) {
                    r[i][j] = arr[i][j];
                }
            }
            return r;
        }
        public boolean isEnd(int[][] board) {
            return board[0][0] == 1 && board[0][1] == 2 && board[0][2] == 3 && board[1][0] == 4 && board[1][1] == 5 && board[1][2] == 0;
        }
    
        public String toString(int[][] arr) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < arr.length; i++) {
                for (int j = 0; j < arr[i].length; j++) {
                    sb.append(arr[i][j]);
                }
            }
            return sb.toString();
        }
    
        public int[][] toArr(String str, int row, int col) {
            int[][] arr = new int[row][col];
            int index = 0;
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    arr[i][j] = Integer.parseInt(str.charAt(index++) + "");
                }
            }
            return arr;
        }
    }
    
    
    
    

  • 相关阅读:
    成为一个优秀的 Python 数据分析师需要哪些知识?
    微信个人号api
    【李航统计学习笔记】第一章:统计学习及监督学习概论
    公司如何防止源代码外泄,保护开发部门代码安全呢?
    Threejs及TypeScript教程
    漫谈:C语言 C++ static究竟是什么
    基于信息融合的风电机组关键部件状态识别
    Spring框架(一)Spring核心,设计理念,创建,优缺点,使用场景···
    Mybatis之foreach
    『现学现忘』Git基础 — 13、Git的基础操作
  • 原文地址:https://blog.csdn.net/liuhongtaowxp1/article/details/126136695