{"id":36,"date":"2018-11-08T16:36:11","date_gmt":"2018-11-08T16:36:11","guid":{"rendered":"https:\/\/andybase.com\/?p=36"},"modified":"2018-11-27T14:41:19","modified_gmt":"2018-11-27T14:41:19","slug":"934-shortest-bridge","status":"publish","type":"post","link":"https:\/\/andybase.com\/?p=36","title":{"rendered":"934 Shortest Bridge"},"content":{"rendered":"\n

link: Shortest Bridge<\/a><\/p>\n\n\n\n

Thought<\/h2>\n\n\n\n

Since the question ask for shortest, so BFS probabely the best algorithms to solve it. But notice, I will use 2 bfs funciton, one to find the edge of first island<\/strong>, the other one is to reach another island based on first edge<\/strong>.<\/p>\n\n\n\n

BFS1:
<\/h4>\n\n\n\n

input: start position
stop condition: queue empty
generate & expansion rule: find all its neighbors, mark as visited, and put ‘1’ to queue -> will put that node in queue for further processing.
put ‘0’ to result queue ->thats what we want to return!<\/p>\n\n\n\n

BFS2<\/h4>\n\n\n\n

input: edge of first island
stop condition: reach any grid with number ‘1’ -> find second island
generate & expansion rule: for any node in que, expend its unvisited neighbors in queue. And also record the level number.<\/p>\n\n\n\n

Code<\/h2>\n\n\n\n
class Solution:\n    def shortestBridge(self, A):\n        \"\"\"\n        :type A: List[List[int]]\n        :rtype: int\n        \"\"\"\n        delta = ((0,1), (1,0), (0,-1), (-1,0))\n        N = len(A)\n        visited = set()\n        def bfs1(x,y):\n            # get the edge of first one\n            visited.add((x,y))\n            que = collections.deque()\n            que.append((x,y))\n            result = collections.deque()\n            while que:\n                c_x,c_y = que.popleft()\n                if A[c_x][c_y] == 0:\n                    result.append((c_x,c_y))\n                    continue\n                for dx,dy in delta:\n                    nx,ny = dx+c_x, dy+c_y\n                    if 0 <= nx <N and 0 <= ny < N and (nx,ny) not in visited:\n                        que.append((nx,ny))\n                        visited.add((nx,ny))\n            return result\n        def bfs2(starts):\n            cnt = 0\n            while starts:\n                siz = len(starts)\n                for i in range(siz):\n                    c_x,c_y = starts.popleft()\n                    if A[c_x][c_y] == 1:\n                        return cnt\n                    for dx,dy in delta:\n                        nx,ny = dx+c_x, dy+c_y\n                        if 0 <= nx <N and 0 <= ny < N and (nx,ny) not in visited:\n                            starts.append((nx,ny))\n                            visited.add((nx,ny))\n                cnt += 1\n        for i in range(N):\n            for j in range(N):\n                if A[i][j] == 1: # find start position \n                    t = bfs1(i,j) # get the edge\n                    return bfs2(t) # get level number<\/pre>\n\n\n\n
Runtime<\/h2>\n\n\n\n
Time: O(n^2)
Space: O(n^2)<\/p>\n","protected":false},"excerpt":{"rendered":"
link: Shortest Bridge Thought Since the question ask for shortest, so BFS probabely the best algorithms to solve it. But […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"enabled":false},"version":2}},"categories":[2],"tags":[4,3],"class_list":["post-36","post","type-post","status-publish","format-standard","hentry","category-leetcode","tag-contest","tag-leetcode"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/paWPni-A","_links":{"self":[{"href":"https:\/\/andybase.com\/index.php?rest_route=\/wp\/v2\/posts\/36","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/andybase.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/andybase.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/andybase.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/andybase.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=36"}],"version-history":[{"count":4,"href":"https:\/\/andybase.com\/index.php?rest_route=\/wp\/v2\/posts\/36\/revisions"}],"predecessor-version":[{"id":79,"href":"https:\/\/andybase.com\/index.php?rest_route=\/wp\/v2\/posts\/36\/revisions\/79"}],"wp:attachment":[{"href":"https:\/\/andybase.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=36"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/andybase.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=36"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/andybase.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=36"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}