JavaInterview JavaInterview
首页
指南
分类
标签
归档
  • CSDN (opens new window)
  • 文档集合 (opens new window)
  • 系统架构 (opens new window)
  • 微信号 (opens new window)
  • 公众号 (opens new window)

『Java面试+Java学习』
首页
指南
分类
标签
归档
  • CSDN (opens new window)
  • 文档集合 (opens new window)
  • 系统架构 (opens new window)
  • 微信号 (opens new window)
  • 公众号 (opens new window)
  • 指南
  • 简历

  • Java

  • 面试

  • 算法

  • algorithm
  • leetcode
JavaInterview.cn
2022-10-07
目录

滑动谜题Java

文章发布较早,内容可能过时,阅读注意甄别。

# 题目

在一个 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]]

提示:

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

# 思路

BFS框架

# 解法


class Solution {

    // 自定义二维数组,0 所在位置的所有相邻索引
    int[][] neighbors = new int[][] {{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}};

    // 交换字符串的方法
    private String exchangeString(String cur, int position, int next) {
        char[] chars = cur.toCharArray();
        char temp = chars[position];
        chars[position] = chars[next];
        chars[next] = temp;
        return new String(chars);
    }

    // 主函数
    public int slidingPuzzle(int[][] board) {
        char[] chars = new char[6];
        int index = 0;
        // 初始化字符串
        for (int[] row: board) {
            for (int col: row) {
                chars[index++] = (char)(col + '0');
            }
        }
        // 初始值
        String start = new String(chars);
        // 目标值
        String target = "123450";
        // 记录步数
        int step = 0;
        // BFS框架开始
        // 用来记录每一步的所有情况
        Queue<String> q = new LinkedList<>();
        // 用来记录走过的情况
        Set<String> visited = new HashSet<>();
        q.offer(start);
        // 寻找最小次数
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                String cur = q.poll();
                // 找到一种解就返回
                if (cur.equals(target)) return step;
                // 找到当前字符串中 0 所在的索引
                int position = cur.indexOf('0');
                // 根据得到的索引定位 0 的相邻字符索引数组
                int[] neighbor = neighbors[position];
                for (int next: neighbor) {
                    // 交换 0 的位置:即交换拼图
                    String exchange = exchangeString(cur, position, next);
                    if (!visited.contains(exchange)) {
                        q.offer(exchange);
                        visited.add(exchange);
                    }
                }
            }
            step++;
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

# 总结

  • 分析出几种情况,然后分别对各个情况实现
微信 支付宝
最近更新
01
1633. 各赛事的用户注册率 Java
07-02
02
1636. 按照频率将数组升序排序 Java
07-02
03
1639. 通过给定词典构造目标字符串的方案数 Java
07-02
更多文章>
Theme by Vdoing | Copyright © 2019-2025 JavaInterview.cn
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式