一、题目

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

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

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

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

点击查看原题
难度级别： 困难

二、思路

1）哈希表+BFS

思路跟752题思路大致相似。
根据当前状态，推断出接下来可能的每一步，并将访问过的状态记录下来，防止多次访问已经访问过的状态，根据状态进行BFS。
如何代表每一种状态？
在这里的思路是使用一个int型，由于是六位数，远小于int型的最大值，可以通过每一个元素占一个十进制位进行表示，确保每个状态都有一个独立的int数值表示。

如何找到下一步的状态？
此处根据表示状态的int还原位二维数组，找到零的位置后，根据零可以与相邻数字交换，从而进行记录一步交换的状态。

三、代码

1）哈希表+BFS

  1. class Solution {
  2.     public int slidingPuzzle(int[][] board) {
  3.         int target = 123450;
  4.         Set<Integer> visited = new HashSet();
  5.         int initalLoc = getStatuInt(board);
  6.         if (initalLoc == target) {    // 查看起点是否目标满足要求
  7.             return 0;
  8.         }
  9.         visited.add(initalLoc);
  11.         int step = 1;
  12.         Queue<Integer> q = new LinkedList();
  13.         q.add(initalLoc);
  14.         while (!q.isEmpty()) {
  15.             int len = q.size();
  16.             while (len-- > 0) {        // 每次将一步的所有可能性遍历完
  17.                 int val = q.poll();
  18.                 List<Integer> nextSteps = getNextStep(val);    // 获取所有下一步的可能性
  19.                 for (int nextStep : nextSteps) {
  20.                     if (visited.contains(nextStep)) {    // 访问过的状态跳过
  21.                         continue;
  22.                     }
  23.                     if (nextStep == target) {
  24.                         return step;
  25.                     }
  26.                     q.add(nextStep);
  27.                     visited.add(nextStep);
  28.                 }
  29.             }
  30.             step++;
  31.         }
  32.         return -1;
  33.     }
  34.     private List<Integer> getNextStep(int val) {
  35.         int[][] board = new int[2][3];
  36.         int offset = 100000;
  37.         int zeroRow = 0, zeroCol = 0;
  38.         for (int i = 0; i < board.length; i++) {
  39.             for (int j = 0; j < board[0].length; j++) {
  40.                 board[i][j] = (val/offset) % 10;
  41.                 offset /= 10;
  42.                 if (board[i][j] == 0) {    // 找到0所在的位置
  43.                     zeroRow = i;
  44.                     zeroCol = j;
  45.                 }
  46.             }
  47.         }
  48.         List<Integer> ans = new ArrayList();
  49.         int[][] directs = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
  50.         for (int[] direct : directs) {
  51.             int newVal = swapGetStatuIntAndRestore(board, zeroRow, zeroCol, zeroRow + direct[0], zeroCol + direct[1]);
  52.             if (newVal != -1) {
  53.                 ans.add(newVal);
  54.             }
  55.         }
  56.         return ans;
  57.     }
  58.     private int swapGetStatuIntAndRestore(int[][] board, int zeroRow, int zeroCol, int anthRow, int anthCol) {
  59.         if (anthRow >= board.length || anthRow < 0 || anthCol >= board[0].length || anthCol < 0) {
  60.             return -1;
  61.         }
  62.         swap(board, zeroRow, zeroCol, anthRow, anthCol);
  63.         int ans = getStatuInt(board);
  64.         swap(board, zeroRow, zeroCol, anthRow, anthCol);
  65.         return ans;
  66.     }
  67.     private void swap(int[][] board, int zeroRow, int zeroCol, int anthRow, int anthCol) {
  68.         int t = board[zeroRow][zeroCol];
  69.         board[zeroRow][zeroCol] = board[anthRow][anthCol];
  70.         board[anthRow][anthCol] = t;
  71.     }
  72.     private int getStatuInt(int[][] board) {
  73.         int ans = 0;
  74.         int offset = 100000;
  75.         for (int[] row : board) {
  76.             for (int i : row) {
  77.                 ans += offset * i;
  78.                 offset /= 10;
  79.             }
  80.         }
  81.         return ans;
  82.     }
  83. }

数组中元素个数为n，时间复杂度为O(n*n!)，空间复杂度为O(``n*n!``)