在一个 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]]
解题思路:使用BFS广度搜索,把二维数组换成字符串,判断是否访问
class Solution { public int slidingPuzzle(int[][] board) { //当前交换次数 int lev = 0; //转换成字符串 String s = toString(board); //BFS队列 Queuequeue = new ArrayDeque<>(); queue.offer(s); //访问过的字符串 Set set = new HashSet<>(); Map map = new HashMap<>(); while (!queue.isEmpty()) { String cur = queue.poll(); int[][] arr = toArr(cur, board.length, board[0].length); //是否结束 if (isEnd(arr)) { return lev; } set.add(cur); int zeroRow = -1; int zeroCol = -1; //寻找0的位置 for (int i = 0; i < arr.length; i++) { for (int j = 0; j < arr[i].length; j++) { if (arr[i][j] == 0) { zeroRow = i; zeroCol = j; break; } } } //上 if (zeroRow > 0) { int[][] board1 = clone(arr); int tmp = board1[zeroRow - 1][zeroCol]; board1[zeroRow - 1][zeroCol] = 0; board1[zeroRow][zeroCol] = tmp; String ss = toString(board1); if (!set.contains(ss)) { queue.offer(ss); map.put(ss, lev + 1); } } //左 if (zeroCol > 0) { int[][] board1 = clone(arr); int tmp = board1[zeroRow][zeroCol - 1]; board1[zeroRow][zeroCol - 1] = 0; board1[zeroRow][zeroCol] = tmp; String ss = toString(board1); if (!set.contains(ss)) { queue.offer(ss); map.put(ss, lev + 1); } } //右 if (zeroCol < 2) { int[][] board1 = clone(arr); int tmp = board1[zeroRow][zeroCol + 1]; board1[zeroRow][zeroCol + 1] = 0; board1[zeroRow][zeroCol] = tmp; String ss = toString(board1); if (!set.contains(ss)) { queue.offer(ss); map.put(ss, lev + 1); } } //下 if (zeroRow < 1) { int[][] board1 = clone(arr); int tmp = board1[zeroRow + 1][zeroCol]; board1[zeroRow + 1][zeroCol] = 0; board1[zeroRow][zeroCol] = tmp; String ss = toString(board1); if (!set.contains(ss)) { queue.offer(ss); map.put(ss, lev + 1); } } String next = queue.peek(); if ((next != null && map.get(next) != lev) || next == null) { lev++; } } return -1; } public int[][] clone(int[][] arr) { int[][] r = new int[arr.length][arr[0].length]; for (int i = 0; i < arr.length; i++) { for (int j = 0; j < arr[i].length; j++) { r[i][j] = arr[i][j]; } } return r; } public boolean isEnd(int[][] board) { return board[0][0] == 1 && board[0][1] == 2 && board[0][2] == 3 && board[1][0] == 4 && board[1][1] == 5 && board[1][2] == 0; } public String toString(int[][] arr) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < arr.length; i++) { for (int j = 0; j < arr[i].length; j++) { sb.append(arr[i][j]); } } return sb.toString(); } public int[][] toArr(String str, int row, int col) { int[][] arr = new int[row][col]; int index = 0; for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { arr[i][j] = Integer.parseInt(str.charAt(index++) + ""); } } return arr; } }