描述

在一个 3×3 的网格中，放着编号 1 到 8 的 8 块板，以及一块编号为 0 的空格。

一次移动可以把空格 0 与上下左右四邻接之一的板子交换。

给定初始和目标的板子排布，返回到目标排布最少的移动次数。

如果不能从初始排布移动到目标排布，返回-1.

在线评测地址

样例 1

输入: [  [2,8,3],  [1,0,4],  [7,6,5] ] [  [1,2,3],  [8,0,4],  [7,6,5] ] 输出: 4  解释: [                 [  [2,8,3],          [2,0,3],  [1,0,4],   -->    [1,8,4],  [7,6,5]           [7,6,5] ]                 ]  [                 [  [2,0,3],          [0,2,3],  [1,8,4],   -->    [1,8,4],  [7,6,5]           [7,6,5] ]                 ]  [                 [  [0,2,3],          [1,2,3],  [1,8,4],   -->    [0,8,4],  [7,6,5]           [7,6,5] ]                 ]  [                 [  [1,2,3],          [1,2,3],  [0,8,4],   -->    [8,0,4],  [7,6,5]           [7,6,5] ]                 ]  

样例 2

输入: [[2,3,8],[7,0,5],[1,6,4]] [[1,2,3],[8,0,4],[7,6,5]] 输出: -1  

使用单向 BFS 算法

public class Solution {     /**      * @param init_state: the initial state of chessboard      * @param final_state: the final state of chessboard      * @return: return an integer, denote the number of minimum moving      */     public int minMoveStep(int[][] init_state, int[][] final_state) {         String source = matrixToString(init_state);         String target = matrixToString(final_state);          Queue<String> queue = new LinkedList<>();         Map<String, Integer> distance = new HashMap<>();          queue.offer(source);         distance.put(source, 0);          while (!queue.isEmpty()) {             String curt = queue.poll();             if (curt.equals(target)) {                 return distance.get(curt);             }              for (String next : getNext(curt)) {                 if (distance.containsKey(next)) {                     continue;                 }                 queue.offer(next);                 distance.put(next, distance.get(curt) + 1);             }         }          return -1;     }      public String matrixToString(int[][] state) {         StringBuilder sb = new StringBuilder();         for (int i = 0; i < 3; i++) {             for (int j = 0; j < 3; j++) {                 sb.append(state[i][j]);             }         }         return sb.toString();     }      public List<String> getNext(String state) {         List<String> states = new ArrayList<>();         int[] dx = {0, 1, -1, 0};         int[] dy = {1, 0, 0, -1};          int zeroIndex = state.indexOf('0');         int x = zeroIndex / 3;         int y = zeroIndex % 3;          for (int i = 0; i < 4; i++) {             int x_ = x + dx[i];             int y_ = y + dy[i];             if (x_ < 0 || x_ >= 3 || y_ < 0 || y_ >= 3) {                 continue;             }              char[] chars = state.toCharArray();             chars[x * 3 + y] = chars[x_ * 3 + y_];             chars[x_ * 3 + y_] = '0';             states.add(new String(chars));         }          return states;     } }  

使用双向 BFS 算法。可以把这份代码当模板背诵。

public class Solution {     /**      * @param init_state: the initial state of chessboard      * @param final_state: the final state of chessboard      * @return: return an integer, denote the number of minimum moving      */     public int minMoveStep(int[][] init_state, int[][] final_state) {         String source = matrixToString(init_state);         String target = matrixToString(final_state);          if (source.equals(target)) {             return 0;         }          Queue<String> forwardQueue = new ArrayDeque<>();         Set<String> forwardSet = new HashSet<>();         forwardQueue.offer(source);         forwardSet.add(source);          Queue<String> backwardQueue = new ArrayDeque<>();         Set<String> backwardSet = new HashSet<>();         backwardQueue.offer(target);         backwardSet.add(target);          int steps = 0;         while (!forwardQueue.isEmpty() && !backwardQueue.isEmpty()) {             steps++;             if (extendQueue(forwardQueue, forwardSet, backwardSet)) {                 return steps;             }              steps++;             if (extendQueue(backwardQueue, backwardSet, forwardSet)) {                 return steps;             }         }          return -1;     }      private boolean extendQueue(Queue<String> queue,                                 Set<String> set,                                 Set<String> targetSet) {         int size = queue.size();         for (int i = 0; i < size; i++) {             String curt = queue.poll();             for (String next : getNext(curt)) {                 if (set.contains(next)) {                     continue;                 }                 if (targetSet.contains(next)) {                     return true;                 }                 queue.offer(next);                 set.add(next);             }         }         return false;     }      public String matrixToString(int[][] state) {         StringBuilder sb = new StringBuilder();         for (int i = 0; i < 3; i++) {             for (int j = 0; j < 3; j++) {                 sb.append(state[i][j]);             }         }         return sb.toString();     }      public List<String> getNext(String state) {         List<String> states = new ArrayList<>();         int[] dx = {0, 1, -1, 0};         int[] dy = {1, 0, 0, -1};          int zeroIndex = state.indexOf('0');         int x = zeroIndex / 3;         int y = zeroIndex % 3;          for (int i = 0; i < 4; i++) {             int x_ = x + dx[i];             int y_ = y + dy[i];             if (x_ < 0 || x_ >= 3 || y_ < 0 || y_ >= 3) {                 continue;             }              char[] chars = state.toCharArray();             chars[x * 3 + y] = chars[x_ * 3 + y_];             chars[x_ * 3 + y_] = '0';             states.add(new String(chars));         }          return states;     } }  

戳我学习更多题解 戳我免费试听算法课程前三章

大佬有話說 (0)