# 733. Flood Fill
###### tags: `Python`,`Leetcode`
## MyCode!
https://leetcode.com/problems/flood-fill/

* 好看的參考影片 : https://www.youtube.com/watch?v=VuiXOc81UDM&t=371s

### Way 1 (DFS)

### Way 2 (BFS)

## 解法
### DFS
#### Step 1 : 設定三個變數
* 長,寬 = m,n
* 以及得知原先 pixel 的顏色為何 (orginal_color)，後續只要是相鄰的 orginal_color 要重新填色填為 color
#### Step 2 : 寫一個 function ，後續須不斷 call function ，把起始的 pixel 填滿後，上下左右也填滿。
* function 中的變數主要兩個(r,c)，為 pixel 的座標
* **當填色遇到某些狀況時需要結束，換個填色方向繼續填**
1. pixel 碰到邊框或是超過編框
2. pixel 座標為負，不符合題目限制
3. 該 pixel 已經被填過新色 / 原本就是新色
4. 該 pixel 原本的顏色不屬於我們要取代的目標

* 如果不是以上四個狀況，即可把該目標 pixel [r][c]，填為 color，並持續 call function 往下、上、右、左不斷填色 **(recursion)**，**實行例子請看參考影片的 3:37 - 4:30**

#### Step 3 : 把起始 pixel 座標丟進去 function ，開始 recursion
#### Step 4 : return image，大功告成

### BFS
#### BFS 的精髓在於 queue，解說請看參考影片的 5:03 - 5:36，每把一個 pixel 塞進 queue ，就會把周圍的也塞進 queue
#### Step 1 : 設定三個變數
* 長,寬 = m,n
* 以及得知原先 pixel 的顏色為何 (orginal_color)，後續只要是相鄰的 orginal_color 要重新填色填為 color
#### Step 2 : 寫一個 funtcion ，去進行 BFS，沒有 recursion ， 只有 iteration
* 要注意 queue 的原意是 FIFO，要把東西拿出來填色，周圍需要填色的 pixel 塞進 queue
* r,c 兩參數為起始 pixel 座標，把座標塞進二維陣列，作為 queue 的要被取出來的頭，以下步驟把頭取出來處理:
#### Step 3 :在 function 中會有一個 while loop 不斷把東西塞進 queue 中，也不斷把 queue 中的東西取出來使用
* 設定兩變數_r,_c = queue.pop(0)。意即把 queue 中最優先處理的東西取出來判斷是否要填色：
1. 遇到以下狀況**不需要**填色：
* pixel 碰到編框或超過編框
* 座標是負的
* pixel 已經被填過新色
* pixel 原本的顏色就不是我們要取代的顏色目標
2. 那如果**需要**填色，把該 pixel 更改顏色後，將左鄰右社排進 queue 處理。
#### Step 4 : 把座標丟進去 function ，開始 bfs
* 當　queue 裡面沒東西的時候，while 迴圈就會停止
#### Step 5 : return image，大功告成
## BFS 與 DFS 於這題的比較（時間複雜度、空間複雜度）
### DFS、BFS
* Time Complexity
1. O(mn)，最慘的狀況就是每一格都要填滿
* Space Complexity
1. O(mn)，原因同上
### DFS 在 flood fill 沒有 BFS 這麼備受推崇
* 因為在做 DFS 時就會需要 stack 放接下來要填色的候選人，要多耗費記憶體