21-6-26 滑动谜题

2024-01-23 22:28:58

滑动谜题难度[困难]

在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示.

一次移动定义为选择 0 与一个相邻的数字（上下左右）进行交换.

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

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

示例：

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

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

输入：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 = [[3,2,4],[1,5,0]]
输出：14

提示：

board 是一个如上所述的 2 x 3 的数组.
board[i][j] 是一个 [0, 1, 2, 3, 4, 5] 的排列.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sliding-puzzle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：BFS

class Solution {
    //用来存储当前的状态和 0 的坐标
    class Node{
        int x,y;
        String str;
        Node(String str_,int x_,int y_){
            str=str_;
            x=x_;
            y=y_;
        }
    }
    //起始和终点
    String s,e;
    //0的坐标
    int x,y;
    //板块 长宽
    int n=2,m=3;
    public int slidingPuzzle(int[][] board) {
        s="";
        e="123450";
        //枚举找出 0 并获取其坐标
        for(int i =0;i<n;i++){
            for(int j =0;j<m;j++){
                s+=board[i][j];
                if(board[i][j]==0){
                    x=i;
                    y=j;
                }
            }
        }
        int ans = bfs();
        return ans;
    }
    //相邻交互的操作数
    int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
    int bfs() {
        Deque<Node> d = new ArrayDeque<>();
        Map<String,Integer> map = new HashMap<>();
        Node root = new Node(s,x,y);
        d.addLast(root);
        map.put(s,0);
        while (!d.isEmpty()){
            Node poll = d.pollFirst();
            int step =map.get(poll.str);
            if(poll.str.equals(e)) return step;
            int dx = poll.x,dy =poll.y;
            //搜索交互相邻字符所得的板块
            for(int []di:dirs){
                int nx = dx+di[0],ny = dy+di[1];
                //越界时 continue
                if(nx<0 || nx>=n || ny<0 || ny >=m) continue;
                String nStr = update(poll.str,dx,dy,nx,ny);
                //已经搜索过 continue
                if(map.containsKey(nStr)) continue;
                Node next = new Node(nStr,nx,ny);
                d.addLast(next);
                map.put(nStr,step+1);
            }
        }
        return -1;
    }
    //交互 操作
    //二维转换一维   idx = x*m + y ，  x = idx/m , y = idx%m;
    String update(String cur, int dx, int dy, int nx, int ny) {

        char [] cs = cur.toCharArray();
        char tmp = cs[dx*m+dy];
        cs[dx*m+dy] = cs[nx*m+ny];
        cs[nx*m+ny] = tmp;
        return String.valueOf(cs);
    }
}

解法二：A*

class Solution {
    class Node {
        String str;
        int x, y;
        int val;
        Node(String _str, int _x, int _y, int _val) {
            str = _str; x = _x; y = _y; val = _val;
        }
    }
    int f(String str) {
        int ans = 0;
        char[] cs1 = str.toCharArray(), cs2 = e.toCharArray();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 跳过「空格」，计算其余数值的曼哈顿距离
                if (cs1[i * m + j] == '0' || cs2[i * m + j] == '0') continue;
                int cur = cs1[i * m + j], next = cs2[i * m + j];
                int xd = Math.abs((cur - 1) / 3 - (next - 1) / 3);
                int yd = Math.abs((cur - 1) % 3 - (next - 1) % 3); 
                ans += (xd + yd);
            }
        }
        return ans;
    }
    int n = 2, m = 3;
    String s, e;
    int x, y;
    public int slidingPuzzle(int[][] board) {
        s = "";
        e = "123450";
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                s += board[i][j];
                if (board[i][j] == 0) {
                    x = i; y = j;
                }
            }
        }

        // 提前判断无解情况
        if (!check(s)) return -1;

        int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
        Node root = new Node(s, x, y, f(s));
        PriorityQueue<Node> q = new PriorityQueue<>((a,b)->a.val-b.val);
        Map<String, Integer> map = new HashMap<>();
        q.add(root);
        map.put(s, 0);
        while (!q.isEmpty()) {
            Node poll = q.poll();
            int step = map.get(poll.str);
            if (poll.str.equals(e)) return step;
            int dx = poll.x, dy = poll.y;
            for (int[] di : dirs) {
                int nx = dx + di[0], ny = dy + di[1];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                String nStr = update(poll.str, dx, dy, nx, ny);      
                if (!map.containsKey(nStr) || map.get(nStr) > step + 1) {
                    Node next = new Node(nStr, nx, ny, step + 1 + f(nStr));
                    q.add(next);
                    map.put(nStr, step + 1);
                }
            }
        }
        return 0x3f3f3f3f; // never
    }
    String update(String cur, int i, int j, int p, int q) {
        char[] cs = cur.toCharArray();
        char tmp = cs[i * m + j];
        cs[i * m + j] = cs[p * m + q];
        cs[p * m + q] = tmp;
        return String.valueOf(cs);
    }
    boolean check(String str) {
        char[] cs = str.toCharArray();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n * m; i++) {
            if (cs[i] != '0') list.add(cs[i] - '0');
        }
        int cnt = 0;
        for (int i = 0; i < list.size(); i++) {
            for (int j = i + 1; j < list.size(); j++) {
                if (list.get(i) < list.get(j)) cnt++;
            }
        }
        return cnt % 2 == 0;
    }
}

关于A*的具体还需要去了解

此文章创于本人学习时的记录，如有错误或更优解还请指出

码农公寓

解法一：BFS

解法二：A*

相关文章