Leetcode-773. 滑动谜题

773. 滑动谜题
在一个 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
解题思路
利用BFS思路，将谜题转换为字符串进行求解（选择就是0和相邻的位置进行交换）

class Solution {
    public int slidingPuzzle(int[][] board) {
        int m=2,n=3;
        String start="";
        String target="123450";
        for(int i=0;i<m;i++){
            for(int j=0;j<3;j++){
                start=start+board[i][j];
            }
        }
        int[][] neighbor=new int[][]{
            {1,3},{ 0, 4, 2 },{ 1, 5 },{ 0, 4 },{ 3, 1, 5 },{ 4, 2 }
        };//这个是自己事先罗列穷举的
        int step=0;
        Queue<String> q=new LinkedList<>();
        Set<String> visited=new HashSet<>();
        visited.add(start);
        q.offer(start);
        while(!q.isEmpty()){
            int sz=q.size();
            for(int i=0;i<sz;i++){
                String cur=q.poll();
                if(cur.equals(target)){
                    return step;
                }
                int idx=cur.indexOf('0');//找到0的坐标
                for(int tmp:neighbor[idx]){
                    String new_cur=cur;
                    new_cur=swap(new_cur,idx,tmp);
                    if(!visited.contains(new_cur)){
                        visited.add(new_cur);
                        q.offer(new_cur);
                    }
                }
            }
            step++;
        }
        return -1;
    }
    public String swap(String board,int idx,int tmp){
        char[] str = board.toCharArray();
        str[idx]=str[tmp];
        str[tmp]='0';
        return String.valueOf(str);
    }
}