# 695. Max Area of Island
###### tags: `Python`,`Leetcode`
## MyCode!
https://leetcode.com/problems/max-area-of-island/

### Way 1 (BFS)

### Way 2 (DFS)
## 解題思路
* **題目提供一個 m*n 的 grid，grid 中有好幾個小島**
1. pixel 值為 1 的相連區塊即為小島
2. 相連定義：上下左右相接的小格，斜接不算
* **找到 grid 中最大的小島，所以我要：**
1. 在 grid 中依序尋找值為 1 的 pixel，並且找到後就開始 BFS 或是 DFS 去計算小島的大小
2. 要不斷比較所算出的小島大小，並更新到最大的狀態
3. BFS 跟 DFS 寫成另外一個 function ，叫來用更方便
* 理論上，時間複雜度應該為 O(mn)
* **在這裡會遇到一些 Variable Scope 的問題，需要複習請看[印度人教學](https://www.programiz.com/python-programming/global-local-nonlocal-variables)：**

1. **Global 全域變數** : 在 function 外的變數，function 內外都可以 access 這個變數
2. **Nonlocal** : 用在 local Scope 未被定義的網狀 function ，所以這個變數既不在 local 也不在 global
3. **Local** : 如果在 function 內宣告一個變數，我們在 function 外就無法 access 它
* 但是在 **leetcode 中題目本身就是一個 function** ，所以我如果**直接宣告**一個變數，**它會是一個 nonlocal**
1. 在 DFS 或是 BFS function 中的變數是 local ， 為了改動到 leetcode 的 "全域"(nonlocal) 變數，需要在 DFS 或是 BFS function 宣告變數 scope 為 nonlocal
2. 呈上， nonlocal scope 既不在 local 也不在 global，所以我如果要在 function 中的 function (DFS,BFS) access 它，NOPE!
## 解法
### Way 1 (BFS)
#### Step 1 : 宣告三個變數
* m,n = 長,寬
* maxArea 用於紀錄目前最大的小島面積
#### Step 2 : 寫一個 BFS 的 function
* 跟 [Flood Fill](https://hackmd.io/@clinicoreport/ry0zCWPvi) 的方法大同小異，不多做贅述，些微不同之處如下三點：
1. 需要宣告 nonlocal grid
2. 並且設定一個變數 currentArea (local) 來計算目前遇到的小島面積多大
3. 經過的 pixel 要改變數值為 0 ，避免二次計算
#### Step 3 : 開始由左而右，由上而下掃視 pixel ，遇到第一個 1 就開始 BFS
* 把當前算到的面積 = currentArea
* 如果 currentArea 比 maxArea 大，把 maxArea 更新為 currentArea 的數值
1. 這樣就可以一直保持 maxArea 是該 grid 中當前面積最大的
### Way 2 (DFS)
#### Step 1 : 宣告四個變數
* m,n = 長,寬
* maxArea 用於紀錄目前最大的小島面積
* currentArea 這次宣告於 nonlocal 是因為後面進行 recursion 時會不斷的 call function ，我不希望 call function 的時候 currentArea 一直被改動到，這樣就不能 +1 +1 的計算面積
#### Step 2 : 寫一個 BFS 的 function
* 跟 [Flood Fill](https://hackmd.io/@clinicoreport/ry0zCWPvi) 的方法大同小異，不多做贅述，些微不同之處如下三點：
1. 需要宣告 nonlocal grid，nonlocal currentarea
2. 變數 currentArea 用於計算目前遇到的小島面積多大(會直接改動到 nonlocal 的變數)
3. 經過的 pixel 要改變數值為 0 ，避免二次計算
#### Step 3 : 開始由左而右，由上而下掃視 pixel ，遇到第一個 1 就開始 DFS
* 把當前算到的面積 = currentArea
* 如果 currentArea 比 maxArea 大，把 maxArea 更新為 currentArea 的數值
1. 這樣就可以一直保持 maxArea 是該 grid 中當前面積最大的
2. 每算完一次小島面積後要把 nonlocal 再次歸零，才能夠再計算下一顆小島面積