[LeetCode] #1091. Shortest Path in Binary Matrix

-

題目

Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1.

A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n - 1, n - 1)) such that:

  • All the visited cells of the path are 0.
  • All the adjacent cells of the path are 8-directionally connected (i.e., they are different and they share an edge or a corner).

The length of a clear path is the number of visited cells of this path.

直覺解

構想：

用遞迴。從 grid[0][0] 的點出發，按照「右下、下、右、左下、右上」的優先順序，依序嘗試下一個點要往哪個方向走，直到走到 grid[n-1][n-1] 或沒路了為止。

python 3 實作（失敗）：

def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int: 

    ans = -1 

    n = len(grid) 

    if grid[n-1][n-1] != 0: 

        return ans 

         

    def findPath(current, ans): 

        i, j = current 

             

        if i >= n or j >=n: 

            return -1 

             

        if grid[i][j] != 0: 

            return -1 

        ans += 1 

             

        if i == n-1 and j == n-1: 

            return ans 

 

        result = findPath((i+1, j+1), ans) 

        if result > 0: 

            return result 

 

        result = findPath((i+1, j), ans) 

        if result > 0: 

            return result 

 

        result = findPath((i, j+1), ans) 

        if result > 0: 

            return result 

 

        result = findPath((i+1, j-1), ans) 

        if result > 0: 

            return result 

 

        result = findPath((i-1, j+1), ans) 

        if result > 0: 

            return result 

        return -1 

         

    current = (0, 0) 

    return findPath(current, 0)

執行結果：

Runtime Error Message: RecursionError: maximum recursion depth exceeded in comparison

過程中犯過的錯誤

  • 忘記設定，如果到達 grid[n-1][n-1] 的話就可以結束。

構想：

改良的地方：放棄遞迴，用 stack。

自己的 python 3 實作（失敗）：

def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int: 

    n = len(grid) 

    if grid[n-1][n-1] != 0: 

        return -1 

         

    stack = [(0, 0, 0)] 

    while stack: 

        i, j, count = stack.pop() 

             

        if i >= n or j >= n: 

          continue 

        if i < 0 or j < 0: 

          continue 

        if grid[i][j] != 0: 

          continue 

                 

        count += 1 

        if i == n-1 and j == n-1: 

                return count 

             

        stack.extend([(i-1, j+1, count), (i+1, j-1, count), (i, j+1, count), (i+1, j, count) ,(i+1, j+1, count)]) 

         

    return -1

執行結果：

Time Limit Exceeded

Last executed input: [[0,1,1,0,0,0],[0,1,0,1,1,0],[0,1,1,0,1,0],[0,0,0,1,1,0],[1,1,1,1,1,0],[1,1,1,1,1,0]]

錯誤發生原因：

  • 因為沒有限制「不能走回頭路」，結果在 grid[3][2] 和 grid[2][3] 之間徘徊，造成無窮迴圈。
  • 只考慮了五個方向，但其實下一步能走的方向總共有八個。

構想：

改良的地方：按照「右下、下、右、左下、右上、左、上、右上」的優先順序，依序嘗試。走過的點，就把值從 0 改成 2，以免走回頭路。

自己的 python 3 實作 （失敗）：

def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int: 

    n = len(grid) 

    if grid[n-1][n-1] != 0: 

        return -1 

         

    stack = [(0, 0, 0)] 

    while stack: 

        i, j, count = stack.pop() 

             

        if i >= n or j >= n: 

            continue 

        if i < 0 or j < 0: 

            continue 

        if grid[i][j] != 0: 

            continue 

             

        grid[i][j] = 2 

        count += 1 

        if i == n-1 and j == n-1: 

            return count 

             

        stack.extend([(i-1, j-1, count), (i-1, j, count), (i, j-1, count), (i-1, j+1, count), (i+1, j-1, count), (i, j+1, count), (i+1, j, count) ,(i+1, j+1, count)]) 

   

    return -1

執行結果：

Wrong Answer

Input: [[0,1,0,0,0,0],[0,1,0,1,1,0],[0,1,1,0,1,0],[0,0,0,0,1,0],[1,1,1,1,1,0],[1,1,1,1,1,0]]

Output: 15

Expected: 14

錯誤發生原因：

  • 在 grid[3][2] 這個點時，最短路徑應該是往右上走，但依照我的優先順序，會變成先往右再往上，於是就多了一步。

構想：

改良的地方：優先順序改成「右下、左下、右上、下、右、左上、左、上」

自己的 python 3 實作 （失敗）：

def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int: 

    n = len(grid) 

    if grid[n-1][n-1] != 0: 

        return -1 

 

    stack = [(0, 0, 0)] 

    while stack: 

        i, j, count = stack.pop() 

 

        if i >= n or j >= n: 

            continue 

        if i > 0 or j > 0: 

            continue 

        if grid[i][j] != 0: 

            continue 
 

             

        grid[i][j] = 2 

                count += 1 

        if i == n-1 and j == n-1: 

            return count 

             

        stack.extend([(i-1, j, count), (i, j-1, count), (i-1, j-1, count),  (i, j+1, count), (i+1, j, count), (i-1, j+1, count), (i+1, j-1, count), (i+1, j+1, count)]) 

             

    return -1

執行結果：

Wrong Answer

Input: [[0,0,0],[0,1,0],[0,0,0]]

Output: 5

Expected: 4

錯誤發生原因：

  • 在 grid[2][1] 這個點時，最短路徑應該是往右走，但依照我的優先順序，會變成先往右上再往下，於是就多了一步。
  • 感覺起來，除了設定優先順序以外，還要設定別的機制，才能每次都找到最短路徑。

研究別人的解

來源：Python BFS

別人的 python 3 實作：

def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int: 

    N = len(grid) 

    dis = [[-1] * N for _ in range(N)] 

    dis[0][0] = 1 

         

    q = [(0, 0)] if grid[0][0] == 0 else [] 

    while q: 

        r, c = q.pop(0) 

        for i, j in [(r+1, c+1), (r+1, c), (r, c+1), (r-1, c+1), (r+1, c-1), (r-1, c), (r, c-1), (r-1, c-1)]: 

            if 0 <= i < N and 0 <= j < N and dis[i][j] == -1 and grid[i][j] == 0: 

                dis[i][j] = dis[r][c] + 1 

                q.append((i, j)) 

                if i == j == N-1: 

                    break 
 

         

    return dis[-1][-1]

效能：

Runtime: 612 ms, faster than 84.87% of Python3 online submissions for Shortest Path in Binary Matrix.
Memory Usage: 14.7 MB, less than 63.06% of Python3 online submissions for Shortest Path in Binary Matrix.

研究別人的實作時，加上的 print：

def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int: 

    N = len(grid) 

    dis = [[-1] * N for _ in range(N)] 

    dis[0][0] = 1 

         

    q = [(0, 0)] if grid[0][0] == 0 else [] 

    while q: 

        print('-------') 

        print(q) 

        r, c = q.pop(0) 

        for i, j in [(r+1, c+1), (r+1, c), (r, c+1), (r-1, c+1), (r+1, c-1), (r-1, c), (r, c-1), (r-1, c-1)]: 

            print(i, j) 

            if 0 <= i < N and 0 <= j < N and dis[i][j] == -1 and grid[i][j] == 0: 

                print('filtered') 

                dis[i][j] = dis[r][c] + 1 

                q.append((i, j)) 

                if i == j == N-1: 

                    break 

         

    return dis[-1][-1]

研究感想：

我的寫法，會在 stack 裡面塞一堆「下一步要往哪個方向」，而且找到方向之後，不會把沒有被選到的方向清空，所以 stack 裡面有很多無用的資訊。但是這個人的寫法就沒有這個問題。

避免走回頭路，我的寫法，是把走過的 cell 值改成 2。他則是做了一個每個 cell 都是 -1 的新 grid，走過的 cell 就改成「這條路的第幾步」（例如，dis[0][0] 固定都是第一步，而最後的回傳值則是 dis[-1][-1]），所以值是 -1 的話代表沒有走過。

他的優先順序是設定成「右下、下、右、右上、左下、上、左、左上」。我如果用這個順序的話，在 [[0,1,0,0,0,0],[0,1,0,1,1,0],[0,1,1,0,1,0],[0,0,0,0,1,0],[1,1,1,1,1,0],[1,1,1,1,1,0]] 這一題會多走一步。以此題目為例，站在 grid[3][2] 時，我的寫法，找到右邊是可以走的時候，就會直接往那裡走了；但是他的寫法，找到右邊是可以走的時候，他還會繼續看右上能不能走、左下能不能走、⋯⋯直到迭代完所有的可能性，等到下一圈 while，因為已經走過的就不能再走了，如果不是最短的路，就沒有路可以走了，這樣就能篩選出最短的路。這個設計真是太精妙了！！！請收下我的膝蓋！！！！怎麼可以這麼強，我好興奮啊啊啊啊！！！！

不過，走到 grid[N-1][N-1] 這格時，其實可以 return dis[-1][-1] 而不是 break，這樣就不用多跑一次 while 迴圈。

拯救我的直覺解

構想：

改良的地方：不要用 stack，改成 queue。從尾巴拿，和從開頭拿，就足以造成失敗或成功的差別，這個領域真是太令人驚嘆了！

python 3 實作（成功）：

def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int: 

    n = len(grid) 

    if grid[n-1][n-1] != 0: 

        return -1 

 

    queue = [(0, 0, 0)] 

    while queue: 

        i, j, count = queue.pop(0) 

 

        if i >= n or j >= n: 

            continue 

        if i < 0 or j < 0: 

            continue 

        if grid[i][j] != 0: 

            continue 

             

        grid[i][j] = 2 

        count += 1 

        if i == n-1 and j == n-1: 

            return count 

             

        queue.extend([(i-1, j-1, count), (i, j-1, count), (i-1, j, count), (i+1, j-1, count), (i-1, j+1, count), (i, j+1, count), (i+1, j, count) ,(i+1, j+1, count)]) 

             

    return -1

效能：

Runtime: 756 ms, faster than 40.96% of Python3 online submissions for Shortest Path in Binary Matrix.
Memory Usage: 14.7 MB, less than 76.74% of Python3 online submissions for Shortest Path in Binary Matrix.

Comments

Post a Comment

Popular posts from this blog

資料關聯

-
以飲料店的商品種類為例，假設我們現在有飲料和杯子兩種資料。 飲料： id name 1 綠茶 2 紅茶 3 青草茶 杯子： id size 1 500 2 600 3 700 一對一（One to One） 若飲料和杯子是一對一的關係，那麼情況就類似這樣： 綠茶只用 500 cc 的杯子裝 紅茶只用 600 cc 的杯子裝 青草茶只用 700 cc 的杯子裝 一種飲料只有一個尺寸的杯子，而且一個尺寸的杯子也只對應到一種飲料。在這種情況下要建立關聯，有下列兩種方式，擇一即可。這兩種做法在技術上效果是一樣的，不過語意解讀上可能不太一樣。 把關聯欄位加在飲料（語意上，是飲料有杯子這個屬性） 把關聯欄位加在杯子（語意上，是杯子有飲料這個屬性） 把關聯欄位加在飲料的資料表： id name cup_id 1 綠茶 1 2 紅茶 2 3 青草茶 3 把關聯欄位加在杯子的資料表： id size drink_id 1 500 1 2 600 2 3 700 3 一對多（One to Many） 若飲料和杯子是一對多的關係，那麼情況就類似這樣： 綠茶用 500 cc、700 cc 的杯子裝 紅茶只用 600 cc 的杯子裝 一種飲料有許多尺寸的杯子，而且一個尺寸的杯子只對應到一種飲料。 或者是這樣： 綠茶、紅茶、青草茶都只用 500 cc 的杯子裝 一個尺寸的杯子對應到許多種飲料，而且一種飲料只有一個尺寸的杯子。 在這種情況下要建立關聯，一般會選擇加在多的那一邊。如果加在少的那一...
Read more

程式設計相關社群、活動

-
網頁開發 網頁開發雜記 PJCHENder網頁開發咩腳 Backend 台灣 (Backend Tw) Taiwan Backend Group Backend.tw (友善版) Google Chrome Developers 語言 Python Taiwan JavaScript.tw Kotlin： Kraftsman：Coding 職人塾 資安 網路攻防戰 資安解壓縮 Infosec Decompress DEVCORE 如何成為駭客 (資安研討會、社群與網路資源篇) Cymetrics Tech Blog （有胡立大大） 台灣電腦網路危機處理暨協調中心 UCCU Hacker HITCON GIRLS 資安人科技網 個人或公司 資料科學家的工作日常 Ant Yi-Feng Tzeng 偷米騎巴哥 John Liu 的軟體工程思維 Will 保哥的技術交流中心 新加坡商鈦坦科技 Line 的技術部落格 區塊鏈李婷婷 、 FB 、 line 群 管理 TGONetworks 91 敏捷開發之路 技術管理者交流社團 課程 軟體開發學習資訊分享 Udemy 限時免費課程 cs50 中文討論區 Lidemy 鋰學院 商業思維學院 未分類 NEX Foundation 台灣未來基金會 iThome FB Daodu Tech 科技島讀 ∞ Lab 無限大實驗室．金融科技第一站 DevOps Taiwan Chatbot Developers Taiwan 軟體開發的疑難雜症交流區 年會 Hacks In Taiwan 台灣駭客年會 FB 台灣資安大會 cybersec 2021 開源人年會 COSCUP 2021 Python 年會 PyCon 2021 ModernWeb 開發者年會 2021 Javascript 開發者年會 FB: JSDC Taiwan 敏捷年會 Agile Summit 20...
Read more

TCP/ IP 通訊協定

-
為什麼要有通訊協定 不同機器之間，若要能夠溝通的話，需要大家都使用相同的語言。所有人都遵守通訊協定，就不會出現語言隔閡。 什麼是 TCP/ IP 通訊協定 要實現「不同機器之間能夠溝通」，從硬體到軟體，有許多工作要完成。為了讓這份工作比較容易進行，所以將工作拆分成好幾個部分，各自獨立完成；以後若要維護的話，哪個部分有問題，只要維修那個部分就好，不必把所有部分都拿出來檢查，降低維修難度。 至於工作到底要怎麼拆分，不同的模型有不同的建議。OSI（Open System Interconnection）模型切成七層工作，DoD（Department of Defense Model）模型則是切成四層，每一層都有不同的通訊協定。雖然目前實作上通常不是採用 OSI 模型，但為了方便理解「不同機器之間能夠溝通」的機制，通常會用 OSI 模型講解，也會試著將 DoD 模型對應到 OSI 模型。 DoD 模型中有許多通訊協定，不過以 TCP、IP 這兩個通訊協定最具有代表性，所以 DoD 模型又稱為 TCP/ IP 模型。TCP 協定對應到 OSI 模型中的傳送層，IP 協定則是對應到網路層。 TCP、IP 通訊協定負責什麼工作 TCP 協定 發送端的 TCP，和接收端的 TCP，會先進行三向交握，確認彼此能夠順利傳輸資料，才正式開始傳輸資料。 我們可以把要傳輸的資料想像成要郵寄的包裹，郵寄時，包裹會有尺寸或重量的限制，同樣地，傳輸的資料也會有大小的限制。如果資料太大了，TCP 會拆分成小包裹，並且幫每個小包裹編號（以便接收端最後能把小包裹還原成大包裹），並注意是否每一個小包裹都成功送達，若沒有成功送達，TCP 會再補上缺少的小包裹。如果資料太小了，TCP 會幫包裹灌水，以符合大小的下限。 IP 協定 IP 位址就像收件地址，以便確認要將包裹送去哪個主機。IP 位址目前有兩種版本，IPv4 用 32 位元儲存地址，IPv6 用 128 位元儲存地址。所以 IPv6 有比較多的地址可以分配給不同的主機。 IPv4 以 IPv4 而言，位址可以切成兩個部分，第一部分代表 Net ID，第二部分代表 Host ID。相同的 Net ID，代表主機位在相同的 IP 網段，相同 IP 網段的主機之間可以用廣播的方式傳遞資料，而不必透過路由。可以從 N...
Read more