{"id":326074,"date":"2021-02-04T12:46:17","date_gmt":"2021-02-04T04:46:17","guid":{"rendered":"http:\/\/4563.org\/?p=326074"},"modified":"2021-02-04T12:46:17","modified_gmt":"2021-02-04T04:46:17","slug":"%e4%b9%9d%e7%ab%a0%e7%ae%97%e6%b3%95-%e5%ad%97%e8%8a%82%e8%b7%b3%e5%8a%a8%e9%9d%a2%e8%af%95%e9%a2%98%ef%bc%9a%e6%bb%91%e5%8a%a8%e6%8b%bc%e5%9b%be-ii","status":"publish","type":"post","link":"http:\/\/4563.org\/?p=326074","title":{"rendered":"\u4e5d\u7ae0\u7b97\u6cd5 | \u5b57\u8282\u8df3\u52a8\u9762\u8bd5\u9898\uff1a\u6ed1\u52a8\u62fc\u56fe II"},"content":{"rendered":"
\n
\n
\n

\u4e5d\u7ae0\u7b97\u6cd5 | \u5b57\u8282\u8df3\u52a8\u9762\u8bd5\u9898\uff1a\u6ed1\u52a8\u62fc\u56fe II <\/h1>\n

<\/p>\n

\n
\u8cc7\u6df1\u5927\u4f6c : hakunamatata11 <\/span> <\/i> 2<\/span> <\/div>\n
<\/div>\n<\/p><\/div>\n<\/p><\/div>\n<\/p><\/div>\n
<\/p>\n

\u63cf\u8ff0<\/strong><\/p>\n

\u5728\u4e00\u4e2a 3×3 \u7684\u7f51\u683c\u4e2d\uff0c\u653e\u7740\u7f16\u53f7 1 \u5230 8 \u7684 8 \u5757\u677f\uff0c\u4ee5\u53ca\u4e00\u5757\u7f16\u53f7\u4e3a 0 \u7684\u7a7a\u683c\u3002<\/p>\n

\u4e00\u6b21\u79fb\u52a8<\/strong>\u53ef\u4ee5\u628a\u7a7a\u683c 0 \u4e0e\u4e0a\u4e0b\u5de6\u53f3\u56db\u90bb\u63a5\u4e4b\u4e00\u7684\u677f\u5b50\u4ea4\u6362\u3002<\/p>\n

\u7ed9\u5b9a\u521d\u59cb\u548c\u76ee\u6807\u7684\u677f\u5b50\u6392\u5e03\uff0c\u8fd4\u56de\u5230\u76ee\u6807\u6392\u5e03\u6700\u5c11\u7684\u79fb\u52a8\u6b21\u6570\u3002<\/p>\n

\u5982\u679c\u4e0d\u80fd\u4ece\u521d\u59cb\u6392\u5e03\u79fb\u52a8\u5230\u76ee\u6807\u6392\u5e03\uff0c\u8fd4\u56de-1.<\/p>\n

\u5728\u7ebf\u8bc4\u6d4b\u5730\u5740<\/p>\n

\u6837\u4f8b 1<\/strong><\/p>\n

\u8f93\u5165: [  [2,8,3],  [1,0,4],  [7,6,5] ] [  [1,2,3],  [8,0,4],  [7,6,5] ] \u8f93\u51fa: 4  \u89e3\u91ca: [                 [  [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] ]                 ]  <\/code><\/pre>\n
\u6837\u4f8b 2<\/strong><\/p>\n
\u8f93\u5165: [[2,3,8],[7,0,5],[1,6,4]] [[1,2,3],[8,0,4],[7,6,5]] \u8f93\u51fa: -1  <\/code><\/pre>\n
\u4f7f\u7528\u5355\u5411 BFS \u7b97\u6cd5<\/p>\n
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;     } }  <\/code><\/pre>\n
\u4f7f\u7528\u53cc\u5411 BFS \u7b97\u6cd5\u3002\u53ef\u4ee5\u628a\u8fd9\u4efd\u4ee3\u7801\u5f53\u6a21\u677f\u80cc\u8bf5\u3002<\/p>\n
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;     } }  <\/code><\/pre>\n
\u6233\u6211\u5b66\u4e60\u66f4\u591a\u9898\u89e3 \u6233\u6211\u514d\u8d39\u8bd5\u542c\u7b97\u6cd5\u8bfe\u7a0b\u524d\u4e09\u7ae0<\/p>\n<\/p><\/div>\n
 \u5927\u4f6c\u6709\u8a71\u8aaa<\/b> (0<\/span>)        <\/div>\n
 <\/div>\n<\/p><\/div>\n<\/p><\/div>\n
    \n
  • \n","protected":false},"excerpt":{"rendered":"
    \u4e5d\u7ae0\u7b97\u6cd5 | \u5b57\u8282\u8df3\u52a8\u9762\u8bd5\u9898\uff1a\u6ed1\u52a8…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[],"tags":[],"_links":{"self":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/326074"}],"collection":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=326074"}],"version-history":[{"count":0,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/326074\/revisions"}],"wp:attachment":[{"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=326074"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=326074"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=326074"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}