# Python-LeetCode 581 第三招 Grid Traversal

「在四方方的花園裡走呀走呀走，東走西走南走北走，不要重複走。」

在網格(Grid)中進行BFS/DFS走訪是常見的題型，本單元介紹如何運用sentinel(哨兵)之類的小技巧，讓Python在網格上的搜尋，跑得又快又優雅。
網格(或格子點)是指一個$m\times n$的區域，每個格子可以走到他的鄰居，鄰居的定義常用4-directional connected，也就是上下左右，也可以定義為八方位。有時以矩陣方式出現，也有用平面幾何的整數座標點方式出現。

在圖論演算法中最基本的就是Graph Traversal，也就是把走得到的點都歷遍一次。包含LeetCode以及其他地方常常出現以Grid替代graph的Traversal，其實Grid就是個平面團，用Grid出題可能是比較容易描述(不必給邊的集合)而且沒學過圖論的也容易理解題目。這一個單元我們來看看Python在Grid Traversal的一些技巧與範例。
一般Graph Traversal主要是兩個演算法，Breadth First Search(BFS)與Depth First Seach(DFS)，有些場合我們不在乎走訪的順序，也可以把BFS簡化，或可稱為Whatever The First (WTF，開玩笑的)。如果是DAG(directed acyclic graph)就再加上topological sort。本單元不談DAG。

BFS與DFS基本的算法步驟這裡就不重複，課本上與網路上很容易找到。在使用時機方面，在需要找距離(無權的邊的最短路徑)時必須使用BFS，其他如找連通區塊、偵測環路或偵測二分圖這些與拜訪順序無關時，都可以用。DFS通常寫成遞迴的形式，程式碼較簡單，但會有遞迴深度與吃記憶體的問題，LeetCode遞迴深度通常是夠的。

我們先來看BFS。

## Python的Grid BFS
剛寫程式的人碰到格子點往往覺得很煩，四個方向要做類似的事情，類似的指令要複製修改四遍；又要偵測邊界不能走到界外。這裡要提供兩個小技巧讓程式簡化，而且可以有常數倍時間加速的小技巧，特別是Python更為簡化。不囉嗦，以下是我喜歡的BFS寫法。

如果格子點是1表示可以走，0不能走，這個範例程式檢查source能否走到dest。程式簡短而清楚，先看一下程式。

# sample input for demo
grid = [[1,1,0,1,1],
        [0,1,1,0,1],
        [1,0,1,1,1]]
source,dest = (0,0),(0,3)
#dest = (2,0)
# boundary 0 to avoid visiting
grid.append([0]*len(grid[0]))
for row in grid: row.append(0)

visit = set() # visited vertex
que = [source]; head=0 # FIFO queue
visit.add(source)
while head<len(que) and dest not in visit:
    r,c = que[head]; head += 1 # pop the first vertices
    # 4 possible adjacent cells
    for nr,nc in ((r-1,c),(r+1,c),(r,c-1),(r,c+1)):
        if grid[nr][nc]==0 or (nr,nc) in visit:
            continue
        que.append((nr,nc))
        visit.add((nr,nc))
        
if dest in visit:
    print('reachable')
else: print('not reachable')

我們來看看到底做了什麼。
* 加sentinel的技巧。sentinel是哨兵的意思，放哨兵站崗省略邊界的檢查與處理是程式中常用的小技巧。本例中，第8 ~ 9行我們把grid的右方與下方圍了**半圈**不能走的0。目的是省略將來的邊界檢查，你可以看到第17行的迴圈中在檢查可以走的鄰居時，我並沒有檢查index的範圍(0<=nr<m and 0<=nc<n)。為什麼只圍半圈而不是應該要圍一圈嗎？原因是我們可以利用python index -1是list最後一個元素的特性，省去左邊與上邊的0。
* 第11行的visit是一個集合，用來記錄哪些點已經拜訪過，避免重複拜訪，這是走訪效率的最重要步驟。這裡用的是集合，也可以用
visit = [[0]*n for i in range(m)]
二維陣列的形式。
* 第12 ~ 13行是初始設一個列表que，將起點放入que並加入visit。這裡用list來做first-in-first-out的queue，記得**必須**用一個變數head紀錄目前的頭端在哪個位置。
* 第14行開始的while迴圈跑到目的點dest已拜訪或que中沒有點為止。一進入迴圈中，先將que中頭端的點取出來並放入r,c，我們放在容器中的是座標的tuple，這裡自動unpack給r,c。第17行檢查4個方向的鄰居，我們用一個迴圈把要做的四個都直接放在迴圈指令上就可以了。這裡用tuple的形式，用list的形式也可以。

四方位檢查另外一種方式是先設4個row與col的差值
dr,dc = [-1,0,0,1],[0,-1,1,0]
然後用迴圈跑四個位置

for d in range(4):
    nr,nc = r+dr[d],c+dc[d]

如果四方位檢查出現的地方不多，兩種方法都差不多好。

**切忌：** 你可以像我這樣用list搭配變數head做佇列，也可以用python的容器queue或deque。在佇列可能很長時，千萬不要用list搭配que.pop(0)來取出第一個元素，基本上這個動作時間複雜度是$O(len(que))$，相當耗時的。

### BFS範例題

[(題目連結) 1162. As Far from Land as Possible (Medium)](https://leetcode.com/problems/as-far-from-land-as-possible/)
在這個題目中，它給了一個$n\times n$的格子點，0代表water而1表示陸地，找出距離最近陸地最遠的水格子，回傳距離值，如無答案回傳-1。

演算法：把所有陸地的格子當作起點(距離0)，用BFS找距離最大的格子點。請注意，求距離必須使用BFS，不能用DFS。
時間複雜度：$O(n^2)$，即格子點數量的線性時間。

下面的程式基本上把上面BFS的模板改一改就行了。

class Solution:
    # bfs from all land
    def maxDistance(self, grid: List[List[int]]) -> int:
        m,n = len(grid),len(grid[0])
        for row in grid: row.append(1)
        grid.append([1]*n)
        que = []; head =0
        dist = {}
        #initial all land with distance 0
        for i in range(m):
            for j in range(n):
                if grid[i][j]:
                    que.append((i,j))
                    dist[i,j] = 0
        if len(que)==0 or len(que)==m*n:
            return -1
        while head < len(que):
            r,c = que[head]; head += 1
            d = dist[r,c]+1
            for nr,nc in ((r-1,c),(r,c-1),(r,c+1),(r+1,c)):
                if grid[nr][nc]==0 and (nr,nc) not in dist:
                    dist[nr,nc] = d
                    que.append((nr,nc))
        return dist[que[-1]]

我們這裡在外圈圍的是1，因為初始過後，我們只會拜訪0的點。
第8行用一個字典dist來存已走點的距離值，第10 ~ 14行將所有陸地格子距離設為0並放入que中。留意兩個數字的座標要做為字典的key必須用tuple不能用list，存取時的寫法可以用
dist[i,j] = 0
來簡化dist[(i,j)]=0 的寫法。
第15行我們對無解的情形做一個特判。本例中我們要的是距離值，BFS每擴展一圈，距離值加1(第19、22行)。

## 無需考慮走訪順序的範例
有些時候我們不需顧慮走訪的順序，例如找連通區塊時，上述的BFS可以稍微修改變得更簡單些。我們以
[(題目連結) 695. Max Area of Island (Medium)](https://leetcode.com/problems/max-area-of-island/description/)
來說明。題目非常簡單：網格中1是土地0是水，找出面積最大的島，四週邊界外假設是水。
這題就是找出每一個連通區塊的大小，取最大值就是答案。可以用BFS/DFS，以下我們用上述BFS的稍微修改版。因為拜訪的順序不重要，我們從que中取點時，用que.pop()，從尾端拿出來，方便又快速，其實是當stack在使用。

class Solution:
    # whatever traversal
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        m,n = len(grid),len(grid[0])
        for row in grid: row.append(0)
        grid.append([0]*n)
        def land(r,c): # return size
            que = [(r,c)]
            grid[r][c] = -1
            area = 0
            while que:
                i,j = que.pop()
                area += 1
                for ni,nj in ((i-1,j),(i+1,j),(i,j-1),(i,j+1)):
                    if grid[ni][nj] == 1:
                        que.append((ni,nj))
                        grid[ni][nj] = -1 #visited
            #end while
            return area
        #end 
        largest = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j]==1:
                    largest = max(largest, land(i,j))

        return largest

我們把走訪寫成副程式，枚舉每一個格子點，如果他的值不是1，我們就呼叫副程式執行一次走訪。這裡我們沒有用另外的字典或表格記錄每一個點是否走過，取而代之的方法是改寫格子點內的值，走過的改成-1(第9行)，在可以破壞原資料的前提下，是一個方便又省記憶體的方法。
對於我們要的答案，區塊大小，可以數一數while迴圈進入的次數即可。

## Depth First Search範例

這一節我們挑選走訪另外一個應用：偵測環路
[(題目連結) 1559. Detect Cycles in 2D Grid (Medium)](https://leetcode.com/problems/detect-cycles-in-2d-grid/description/)
Grid是以字串的形式傳入，每一個row是一個長度$n$的字串，總共有$m$個字串構成一個$m\times n$的網格。字串是由小寫字母構成，要找是否有相同字母構成的環路，環路的定義是長度至少為4，四方位連通的環路。以下是一個範例
因為在網格上三個格子是不可能構成頭尾相接的環路，因此長度$\geq 4$的意思就是排除長度2(兩個相鄰格子)。Graph上的cycle可以用dfs走訪來偵測，如果到一個點時，他的鄰居中有已經探訪過的鄰居(除了它的DFS parent)，那麼就是找到一個存在的cycle。
以下是範例程式。

class Solution:
    def containsCycle(self, grid: List[List[str]]) -> bool:
        m,n=len(grid),len(grid[0])
        for row in grid: row.append('$')
        grid.append(['$']*n)
        visit = set() #if visited
        def dfs(v,p): # tuple (r,c) node v with parent p
            r,c = v
            ch = grid[r][c]
            for nr,nc in ((r-1,c),(r+1,c),(r,c-1),(r,c+1)):
                if (nr,nc)==p or grid[nr][nc]!= ch: continue
                if (nr,nc) in visit: #cycle found
                    return True
                visit.add((nr,nc))
                if dfs((nr,nc),v): return True
            return False
        #
        for i in range(m):
            for j in range(n):
                if (i,j) not in visit and dfs((i,j),(-1,-1)): 
                    return True
        return False  
        

第4 ~ 5行我們一樣圍半圈邊界，用一個題目中不會出現的字元。然後寫一個遞迴的DFS。傳入的包含目前的點，還包括他的parent。在此DFS中我們會探訪某個字元相連通的所有相同字元的格子，如果發現環路會回傳True，否則回傳False。在第11行我們先排除parent以及字元不同的鄰居，第12行發現鄰居是探訪過的，也就是發現環路了。其他用到的技巧與前面的BFS都類似。
在主程式中，我們掃描所有格子點。如果還沒有探訪過，就會由該點開始進行一次DFS，初始的parent給一個不可能的位置即可。請注意Python一樣有*short-circuit evaluation*---邏輯判斷式已經確定後不會運算後半部的判斷式。
這裡(第20行)的情形if是and組合的判斷式，如果前面的"(i,j) not in visit"為假，後面的DFS就不會呼叫。這種情形在list或dict使用時很重要，if中一定要先確認範圍或key值存在才能取用，否則便會出現index出界或keyError。

## Hard-BFS

本單元最後我們挑選一題難度為Hard的題目
[(題目連結) 1293. Shortest Path in a Grid with Obstacles Elimination (Hard)](https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/)
給一個網格，裡面0的格子表示可以通行，1表示障礙物。要從左上角走到右下角，每一步可以移到目前格子上下左右四個相連的鄰居。通行的格子當然可以走，障礙物的格子必須將障礙物敲碎才能通行。請問，在最多敲碎$k$個障礙物格子的條件下，最短的路徑長度為何？

這題有DP的味道。
我們把打碎障礙物當作是成本，對於到達一個格子的狀態就有兩個參數：起點的距離d與花費的成本cost。對於相同格子的兩種狀態$(d_1,cost_1)$與$(d_2,cost_2)$，如果$d_1\geq d_2$ and $cost_1 \geq cost_2$，那麼第一個狀態又貴又遠，是沒用的。但如果成本高的距離短，就無法分辨兩者的優劣了。我們必須把他們都記錄下來。
也就是說，對任一點，我們需要紀錄各種成本($0\ldots k$)下的最短距離。
看一下參數範圍，$m,n \leq 40$，$1\leq k\leq mn$，那麼$kmn\leq 40^4$，看起來有點大...。

被唬了嗎？
從左上走到右下角的最短路徑長度是$m+n-2$，中間經過$m+n-3$個格子，起點終點保證沒有障礙物，所以如果$k\geq m+n-3$，那就是吃了無敵星星，不用管障礙物一定可以用最短路徑走到終點。因此，$k$的最大值是$m+n-4$。
我們把每個點想成有$k+1$個分身，也就是一個點狀態用$(r,c,cost)$表示，除了座標之外還有一個所花的成本。我們還是走BFS，但每個點只留有用的狀態，也就是說一個點$(r,c)$允許被重複走到，但只有在成本比較小的時候才會走。例如目前$(r,c,5)$的最短距離是10，那麼如果有條新的路走到$(r,c)$的最短距離是12，但成本是4，那就將它納入；但如果距離12成本5，就不予考慮。
以下是完整的範例程式。

class Solution:
    #BFS, distance increasing, revisiting only with smaller cost
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        m,n = len(grid),len(grid[0])
        if k>=m+n-3: return m+n-2
        oo = m*n+1
        for row in grid: row.append(oo)
        grid.append([oo]*n)
        mincost = [[k+1]*(n+1) for i in range(m+1)]
        que = [(0,0,0,0)] #(r,c,d,cost)
        head = 0
        while head<len(que):
            r,c,d,cost = que[head]; head += 1
            if (r,c) == (m-1,n-1): return d
            for nr,nc in ((r-1,c),(r,c-1),(r,c+1),(r+1,c)):
                mycost = cost+grid[nr][nc]
                if mycost<mincost[nr][nc]:
                    que.append((nr,nc,d+1,mycost))
                    mincost[nr][nc] = mycost
        return -1
 

在第5行先做一個特判，如果$k$很大就不必計算了。然後我們也是在邊界圍半圈，grid本來是個0/1矩陣，我們邊界外圍一個非常大的值，將來把grid[r][c]當作進入這個點的成本：0不須成本，1需要花一塊錢，oo就不會進入。
我們把所有待搜尋狀態放在que中，每一個狀態是$(r,c,d,cost)$表示到達某一點的距離與成本，que中的距離將是單調上升的；另外用一個mincost二維陣列存每個點目前可以到的最小成本，初值設為不可能的大($k+1$)。因為距離值會逐步上升，所以成本要下降才會進入該點。
接著就是BFS的while迴圈。進入時取出一點的狀態(第13行)，檢查是否到達目標(第14行)，探訪鄰居(第15行)。第16行的mycost是這次要進入該鄰居的成本，第17行過濾只有成本下降才會再次走訪(納入que中)。因為距離是逐步上升的，所以第一次碰到終點就是答案，而while迴圈跑完都沒有碰到就是沒有答案。
這題有點難。

## 結語

BFS與DFS是常用的圖形走訪演算法，必須先對基本型的演算法必須有充分的了解。
LeetCode中有很多是在Grid這種特殊圖上的，對於Grid的走訪我們有一些小技巧，可以讓程式更簡潔也更有效率(常數倍)，對Python尤其適合。
BFS與DFS個有不同用途，有時必須使用某一種，有時兩者皆可，也有時隨便順序的走訪。但通常都要避免重複走訪。
BFS/DFS要記錄狀態來避免重複走訪，有時可用二維陣列，有時可以用字典或集合。
最後我們也看到一個複雜的例子是一個點有多種狀態的BFS走訪。