[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

Alpha Camp 全端開發課程學習心得

-
我喜歡邏輯，在哲學系求學時期，我花最多時間的科目，是形式邏輯。但是我一直不明白這個我相對擅長的科目，到底能用在什麼地方。我的邏輯能力，並沒有好到足夠讓我走上學術研究的路，那麼，或許我可以試著寫程式？ 學生時期的我，自認沒有錢，但是有時間。捨不得花錢去上程式設計課程，寧願自己找資源學習。去上過一些免費的程式入門課程，c++ 和 python，對我而言不是很難，但是學完之後，我還是看不出來，要怎麼靠學到的東西解決生活中遇到的問題，漸漸地就沒有動力繼續學下去。 直到出社會，存了點錢，也漸漸體會到時間的重要，終於捨得花錢投資自己，到 Alpha Camp 上專業的課程，而不是無頭蒼蠅自己亂找一通，省下許多時間，也看到自己學的東西是真的能用的，讓我有動力繼續學下去。 我還記得學到串接 api 的時候，心裡真是太激動了。以前在學免費課程時，就隱約有種「我寫的程式，範圍只侷限在我的電腦上」的貧瘠感覺，而在知道了 api 後，發現「我寫的程式可以跟世界接上線了」，頓時覺得自己非常富有。不過，後來才知道，串別人的 api 服務通常是要付費的。 大概是受了形式邏輯的影響，我在學習程式語言時，總是試圖去辨認，哪些東西是比較基本的，基本的東西是透過什麼樣的規則組合出複雜的東西。例如，變數、array、for 迴圈和 function 是基本的東西，可以用這些基本的東西組合出 array 的 reduce 方法，像這樣： function mimicReduce(array, reducerFunction, initialValue) {     if (initialValue) {         let accumulator = initialValue         for (let i = 0; i < array.length; i++) {             accumulator = reducerFunction(accumulator, array[i])         }         return accumulator     } else {         let accumulator = array[0]         for (let i = 1; i < array.length; i
Read more

在 javascript 用 regular expression 為金額加上千位數分隔符號

-
 為了方便使用者快速判斷金額，所以想加上千位數分隔符號。例如： 3000 --> 3,000 3000000 --> 3,000,000 搜尋資料後，結論： 如果數字有小數點的話，可以用  const amount = '3000.00' amount.replace(/\B(?<!\.\d*)(?=(\d{3})+(?!\d))/g, ',') 參考資料： Javascript之數值千分位符號（Comma）的顯示 如果沒有小數點的話，可以用  const amount = '3000' amount.replace(/\B(?=(\d{3})+(?!\d))/g, ',') 參考資料： [Javascrpt]轉換數字成含千分位的文字   不過這個鬼畫符的語法我完全看不懂，查資料的時候一度不肯相信這是真正的程式碼呢⋯⋯因緣際會在讀書會中，得到 Helix 同學提示的關鍵字「 regular expression」，決定試著弄懂，「amount.replace(/\B(?=(\d{3})+(?!\d))/g, ',')」到底是什麼意思。 一、 String.prototype.replace() - MDN 範例：我不小心把 world 拼成 word，想要把句子裡所有的 word 都替換成  world。 const text = 'Hello word! Hello word!' console.log(text.replace('word', 'world')) 結果印出 Hello world! Hello word! 很不幸地，只有第一個錯字有替換，其他錯字都被放生了。如果想要替換全部的 word，就要這樣寫： const text = 'Hello word! Hello word!' console.log(text.replace( /word/ g , ' world '))
Read more

shop_platform - sqlalchemy.exc.TimeoutError

-
發生的問題 啟動伺服器後，第二十一次請求「需要查詢資料庫」的頁面時，會出現「sqlalchemy.exc.TimeoutError: QueuePool limit of size 10 overflow 10 reached, connection timed out, timeout 30.00 (Background on this error at: https://sqlalche.me/e/14/3o7r )」的錯誤訊息。如果請求是不需要查詢資料庫的（例如靜態檔案或前往登入頁面），就不會發生此錯誤。 把 size 和 overflow 設定成更小的數字，可以更快重現這個錯誤 。 感覺起來，就像查詢完資料庫以後，沒有把 connection 釋出一樣，導致「size + overflow」是多少，就只能查詢多少次資料庫。 發現瀏覽器每向伺服器請求一次「需要查詢資料庫」的頁面，在 MySQL Workbench 用 show PROCESSLIST; 指令的查詢結果就會多出一筆資料，筆數達到 size + overflow 時，若再次請求「需要查詢資料庫」的頁面，就會噴 QueuePool limit of size 10 overflow 10 reached 的錯誤。關閉伺服器時，那幾筆資料才會被刪除。 嘗試過但失敗的方法 app.run(debug=False) 自己註冊一個關閉 session 的函式 @app.teardown_appcontext # 改成 @app.teardown_request 也沒用 def teardown_db(exception): db.session.remove() # 改成 db.session.close() 也沒用 print('***** session.remove') # 這一行有印出來，所以此函式有被執行 把 FLASK_ENV=development 拿掉 ，於是 FLASK_ENV 變成預設的 production app.config["SQLALCHEMY_COMMIT_ON_TEARDOWN"] = True 終於成功的方法 第一種方法：用 Ap
Read more