{"id":443541,"date":"2021-04-19T10:56:06","date_gmt":"2021-04-19T02:56:06","guid":{"rendered":"http:\/\/4563.org\/?p=443541"},"modified":"2021-04-19T10:56:06","modified_gmt":"2021-04-19T02:56:06","slug":"%e9%98%bf%e9%87%8c%e5%b7%b4%e5%b7%b4%e9%9d%a2%e8%af%95%e9%a2%98%ef%bc%9a%e9%87%91%e5%ad%97%e5%a1%94","status":"publish","type":"post","link":"http:\/\/4563.org\/?p=443541","title":{"rendered":"\u963f\u91cc\u5df4\u5df4\u9762\u8bd5\u9898\uff1a\u91d1\u5b57\u5854"},"content":{"rendered":"<div>\n<div>\n<div>\n<h1>                  \u963f\u91cc\u5df4\u5df4\u9762\u8bd5\u9898\uff1a\u91d1\u5b57\u5854               <\/h1>\n<p> <\/p>\n<div>\n<div> <span>\u8cc7\u6df1\u5927\u4f6c : zzzrf <\/span>  <span><i><\/i> 9<\/span> <\/div>\n<div> <\/div>\n<\/p><\/div>\n<\/p><\/div>\n<\/p><\/div>\n<div isfirst=\"1\"> <\/p>\n<h2>[\u9898\u76ee\u63cf\u8ff0\u53ef\u4ee5\u770b\u8fd9\u91cc]<\/h2>\n<h2>\u89e3\u9898\u601d\u8def\uff1a\u53cc\u5411 BFS<\/h2>\n<ul>\n<li>\n<p>\u5206\u522b\u4ece\u8d77\u70b9\u548c\u7ec8\u70b9\u5f00\u59cb BFS\uff0c\u8bb0\u5f55\u5404\u81ea\u72b6\u6001\u4e0b\u7684\u6700\u5c11\u6b65\u6570\u3002\u4e24\u4e2a\u72b6\u6001\u4e2d\u9014\u76f8\u9047\u65f6\uff0c\u4e24\u4e2a\u72b6\u6001\u7684\u6700\u5c11\u6b65\u6570\u4e4b\u548c\u5c31\u662f\u7b54\u6848\u3002<\/p>\n<\/li>\n<li>\n<p>\u56e0\u4e3a\u9898\u76ee\u9650\u5b9a\u6700\u591a 20 \u6b65\uff0c\u6240\u4ee5\u4ece\u8d77\u70b9\u548c\u7ec8\u70b9\u5f00\u59cb\u53ea\u9700\u8981\u5404\u8d70\u6700\u591a 10 \u6b65\u3002<\/p>\n<\/li>\n<li>\n<p>\u91d1\u5b57\u5854\u6570\u7ec4\u8fdb\u5165\u54c8\u5e0c\u524d\uff0c\u8981\u5148\u5e8f\u5217\u5316\u6210\u5b57\u7b26\u4e32\u3002\u56e0\u4e3a\u7ed9\u5b9a\u7684\u91d1\u5b57\u5854\u6570\u7ec4\u4e0d\u89c4\u5219\uff0c\u4e0d\u50cf\u534e\u5bb9\u9053\u7684\u6b63\u65b9\u5f62\uff0c\u6240\u4ee5\u6211\u628a\u5b57\u7b26\u4e32\u53cd\u5e8f\u5217\u5316\u540e\u518d\u79fb\u52a8 0 \u7684\u4f4d\u7f6e\u3002\u8fd9\u79cd\u529e\u6cd5\u6bd4\u8f83\u6613\u61c2\uff0c\u4e5f\u8bb8\u5b58\u5728\u66f4\u76f4\u63a5\u7684\u6570\u5b66\u529e\u6cd5\u3002<\/p>\n<\/li>\n<li>\n<p>state \u8bb0\u5f55\u5f53\u524d\u72b6\u6001\uff0crc \u8bb0\u5f55 0 \u7684\u5ea7\u6807\uff0cfrom_start \u8bb0\u5f55\u5f53\u524d\u72b6\u6001\u4ece start \u5f00\u59cb\u8fd8\u662f\u4ece end \u5f00\u59cb\u3002<\/p>\n<\/li>\n<\/ul>\n<pre><code>import itertools from collections import deque  class Solution:     \"\"\"     @param a: the number admiral     @return: the number of steps to return to the original state     \"\"\"     def getSteps(self, a):         start = self.serialize(a)         end = self.serialize([[0], [1,1], [2,2,2], [3,3,3,3], [4,4,4,4,4], [5,5,5,5,5,5]])         start_r, start_c = self.find_zero(a)                  queue = deque([(start, start_r, start_c, True), (end, 0, 0, False)])         distances_from_start, distances_from_end = {start : 0}, {end : 0}                  while queue:             state, r, c, from_start = queue.popleft()             # Meet in the middle             if (from_start and state in distances_from_end) or                  (not from_start and state in distances_from_start):                 return distances_from_start[state] + distances_from_end[state]             # Move to the next state from start \/ end             for next_state, i, j in self.get_next(state, r, c, from_start, distances_from_start, distances_from_end):                 if from_start:                     distances_from_start[next_state] = distances_from_start[state] + 1                     # Maximum 10 steps from start                     if distances_from_start[next_state] &lt;= 10:                         queue.append((next_state, i, j, from_start))                 else:                     distances_from_end[next_state] = distances_from_end[state] + 1                     # Maximum 10 steps from end                     if distances_from_end[next_state] &lt;= 10:                         queue.append((next_state, i, j, from_start))                  return -1          def get_next(self, state, r, c, from_start, distances_from_start, distances_from_end):         a = self.deserialize(state)         for i, j in [(r - 1, c), (r + 1, c), (r - 1, c - 1), (r + 1, c + 1)]:             if 0 &lt;= i &lt; len(a) and 0 &lt;= j &lt; len(a[i]):                 next_state = self.swap(a, r, c, i, j)                 if (from_start and next_state not in distances_from_start) or                      (not from_start and next_state not in distances_from_end):                     yield next_state, i, j          def swap(self, a, r, c, i, j):         a[r][c], a[i][j] = a[i][j], a[r][c]         ret = self.serialize(a)         a[r][c], a[i][j] = a[i][j], a[r][c]         return ret      def find_zero(self, a):         for r in range(len(a)):             for c in range(len(a[r])):                 if a[r][c] == 0:                     return r, c         return -1, -1      def serialize(self, a):         return \"\".join(map(str, itertools.chain(*a)))          def deserialize(self, s):         ret = []         index = 0         for i in range(1, 7):             line = []             for j in range(i):                 line.append(s[index + j])             index += i             ret.append(line)         return ret <\/code><\/pre>\n<\/p><\/div>\n<div> <b>\u5927\u4f6c\u6709\u8a71\u8aaa<\/b> (<span>0<\/span>)        <\/div>\n<div> <\/div>\n<\/p><\/div>\n<\/p><\/div>\n<ul>\n<li>\n","protected":false},"excerpt":{"rendered":"<p>\u963f\u91cc\u5df4\u5df4\u9762\u8bd5\u9898\uff1a\u91d1\u5b57\u5854 \u8cc7\u6df1\u5927\u4f6c &hellip;<\/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\/443541"}],"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=443541"}],"version-history":[{"count":0,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/443541\/revisions"}],"wp:attachment":[{"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=443541"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=443541"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=443541"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}