LeetCode773. 滑动谜题

在一个 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 = [[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

**BFS算法：**把问题抽象成图，从一个点开始，向四周扩散，并且用队列将一个节点周围的所有节点都加入队列。

为了方便，将原来的二维矩阵转换成一维数组进行操作。

可以将问题转换为：每次先找到数字0，然后和周围得数字进行交换，形成新的局面加入队列，当第一次到达target时，就得到了赢得数字游戏的最少步数。

关键点：将2*3的二维数组board压缩成一个一维字符串，二维数组有”上下左右“的概念，压缩成一维数组之后，需要通过设置一个映射来得到某一个元素的上下左右的索引。

neighbor = {{1,3}, {0,2,4}, {1,5}, {0,4}, {1,3,5}, {2,4}};

package com.liyalei.day2;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class Solution {
  //二维转化成一维之后的索引映射
    int[][] neighbor = {{1,3}, {0,2,4}, {1,5}, {0,4}, {1,3,5}, {2,4}};

    public int slidingPuzzle(int[][] board){
        int m = 2, n = 3;
        StringBuilder stringBuilder = new StringBuilder();
        for(int i = 0; i < m; i++){
          //将数组转化成字符串
            for(int j = 0; j < n; j++){
                stringBuilder.append(board[i][j]);
            }
        }
        String start = stringBuilder.toString();
        String target = "123450";

        Queue<String> q = new LinkedList<>();
        Set<String> visited = new HashSet<>();

        q.offer(start);
        visited.add(start);
        int step = 0;
        while (!q.isEmpty()){
            int sz = q.size();
            for(int i = 0; i < sz; i++){
                String cur = q.poll();
              //得到目标直接返回结果
                if(target.equals(cur)) return step;

                int pos = cur.indexOf('0');
                for(int adj : neighbor[pos]){
                    String new_board = swap(cur, adj, pos);
                    if(!visited.contains(new_board)){
                      //避免重复，防止走回头路
                        visited.add(new_board);
                        q.offer(new_board);
                    }
                }
            }
            step++;
        }
        return -1;
    }

    public String swap(String str, int src, int dst){
        char[] arr = str.toCharArray();

        char temp = arr[src];
        arr[src] = arr[dst];
        arr[dst] = temp;

        return new String(arr);
    }
}