從LeetCode學演算法 - 113 BFS (4) / Queue (5)

1091. Shortest Path in Binary Matrix (Medium)

寫在前面

目前0元挑戰賽 的活動已經開始囉！
只要修課後三個月內完課且成功錄取新工作並撰寫心得，
課程就會全額退費喲！請使用下面連結看更詳細的規則說明：

(新年優惠套組已截止囉！）

零元求職挑戰賽 Python 組｜從 LeetCode 學演算法 + 面試成功指南 http://bit.ly/zeroclg

抽獎活動還在繼續累積人數(現在好像沒有人想抽XD)
在Python Taiwan的連結第100篇的文章 底下，
公開分享到你的臉書、按讚該篇文章、並留言告訴我說，
「你最喜歡這一整個系列的哪一篇？為什麼？」或
「除了從LeetCode學演算法系列以外，
你還想要看到關於什麼方向的文章？」
超過20則留言的話 (有完成以上步驟的才算)，我們就抽一組
「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」
課程的免費兌換券進行贈送！

期限嘛…就延長到滿人數吧XDD (不然也沒辦法哈哈)

容筆者工商一下，
「從Leetcode學演算法｜進階篇」 開放預購啦！
這次選了40道難度加深的LeetCode題目，
同樣也會細部解說對應的技巧及須要掌握的演算法！
同時這次購買進階篇的話，
額外還加贈**「從Leetcode學演算法｜面試篇」** ！
當中包含了面試準備須知分享 ，及訪談國內外不同經驗的工程師 ，
讓你不論是想走前端/後端/一般軟工 或者是想找國外的工作 ，
是初學想轉職 還是正在工作 ，都能夠從中得到收穫呦！
有興趣的朋友可以使用下面的早鳥優惠～
「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」 ：
https://bit.ly/leetcodeadv

Question

In an N by N square grid, each cell is either empty (0) or blocked (1).

A clear path from top-left to bottom-right has length k if and only if it is composed of cells C_1, C_2, ..., C_k such that:

Adjacent cells C_i and C_{i+1} are connected 8-directionally (ie., they are different and share an edge or corner)
C_1 is at location (0, 0) (ie. has value grid[0][0])
C_k is at location (N-1, N-1) (ie. has value grid[N-1][N-1])
If C_i is located at (r, c), then grid[r][c] is empty (ie. grid[r][c] == 0).

Return the length of the shortest such clear path from top-left to bottom-right. If such a path does not exist, return -1.

Example 1

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

1
Output: 2

Example 2

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

1
Output: 4

Note:

1 <= grid.length == grid[0].length <= 100
grid[r][c] is 0 or 1

分析/解題

在一個N x N的平方格子裡，每個格子可能是空的(0)，
不然就是阻塞住的(1)。

一個乾淨的路徑從左上到右下的長度為k，如果路徑上的格子都是8方向(也就是九宮格的對應)相連，且開頭是(0, 0)，結尾是(N-1, N-1)，且每一格都是空的(0)。請回傳從左上到右下最短的乾淨路徑長，若不存在則回傳-1。

這個題目其實可以有很多種不同的解決方式，
不過我們好久沒有使用到BFS了，就來試試看BFS的解法吧！
根據題目的定義，我們要找的是最短路徑，
所以可以從(0, 0)開始嘗試每次往8個方向各走一步，
並且將計數+1及標記已經走過，當在某步碰到了(N-1, N-1)時，
即表示我們找到了最短路徑(因為所有路線都是每次同時走一步)。
因此，我們需要一個Queue來記錄當前所有走到的點，
然後每次再將Queue的點取出，
找到8個方向的新的一步的點，加入到Queue中。
(不能超出邊界，不能已經走過，也不能被阻擋住)

那麼我們怎麼知道同一層的要做到哪裡呢？
很簡單，在這層開始之前，我們先記錄下當前Queue的長度，
這樣子同一層只要做完這麼多個點就可以啦！

依此，寫成程式碼如下：
(下面的程式碼中，我們直接把走過的路徑給標成block了，
這點相對較節省空間也較方便，但其實不是很正規，
如果面試時沒有說你可以動grid，請開出一個N x N的visited格子，
用來記錄有經過的點會比較好呦！)

Java

Java的部分，首先我們先檢查grid的狀況，
以及左上右下是否有阻擋住的狀況，有的話就直接回傳-1。
接著使用LinkedList作為我們的Queue，
可以使用add或者offer來加入新的元素。
當queue不為空時，每次取出一個點，往對應的8個方向取點並檢查：

走到右下角的話代表走完，直接回傳cnt。
如果點是合法的點的話，就將那格標記為1並加入queue中。
每輪做完別忘記將cnt遞增。

全部做完還沒有碰到右下角，代表沒有解，回傳-1。

Python

Python的部分則使用deque來操作，
留意到這個題目其實也可以擴展成矩形，
這邊示範使用r, c的方式來記錄，但其實區別不大。
但對deque來說，取出記得是使用popleft，請不要誤用成pop了！

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(N²)/O(N²)，最糟糕的狀況是擴散的很開的時候，
queue所需要的空間會很大，這個問題其實可以使用bi-directional的BFS來降低擴散的程度，可以再參考leetcode上別人的解法。)

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~

想看看其他題目嗎？
歡迎從第零篇 找你想要的！

同時追蹤粉專以獲得更多新文章的通知：
跟著Desolve學程式

另外，「從Leetcode學演算法｜基礎篇」 已經回原價囉，
先前的優惠碼會失效，但這邊仍然為讀者保留了300塊的折抵，
雖然整捆一起買總體比較划算 (差290而已就有整組了阿XD)，
如果你還是想先試試基礎課的話，
300元折抵的連結 在這邊：
https://bit.ly/1desolve