Flood Fill 解題經驗談

第一次接觸到 Flood Fill 這個演算法題型時，我連題目都看不太懂，後來經過一些搜尋及研究才了解，Flood Fill 如名所義，就是洪水淹蓋的意思。

你用過小畫家的一個油漆桶的功能嗎？這個功能就是讓相連同顏色的所有區域變成油漆桶要指定的區域，而這就是 Flood Fill。

了解完題目後，就要來解題，才發現，真的不簡單。

以程式碼解釋題型

用程式碼來顯示題型，就會像是一個 2X2 的 array 所形成的 2D 平面圖，而每一個座標上會標示一個整數，舉例來說長得像這個。

111

010

012

而這個 2D 圖就是代表這個 array， [[1,1,1],[0,1,0],[0,1,2]]。假設我們起始的位置是[1,1]，也就是正中間的這個數字，我們要讓所有連接數字一樣的全部換成另外一個數字，假設是 2 好了，會變成。

222

020

022

在寫任何程式碼以前，光是想出解題的邏輯就相當困難。

所以，我暫時解不開，我只想到一個方案，就是先解解看 1D 的 Flood Fill。

所謂的 1D Flood FIll 就是原本的 2D 變成 1D。這樣，題目就變得簡單多了。假設這個 array [1,0,1,1,1,0,0,1]，的第4個數字連接的全都要變成 2 ，就會變成 [1,0,2,2,2,0,0,1]。

我想到的解題方法就是，先往右檢查到底，直到沒有同數字的再回到原點，向左檢查。

1D 版本的 Flood Fill 解完後，我來嘗試原本的版本。

我到參考邏輯跟解 1D 的版本一致，就是先又在作，然後在向上向下移動，但是，這樣的話會有很多需要轉彎的地方數字改變不到，按下方按鈕看結果。

最後我想到最土法煉鋼的方式，就是從原點出發，然後依上、右、下、左順序，依序檢查是否有與上原點連接相同數字，然後記錄起來，在重紀錄起來的座標中重複檢查上、右、下、左方向的連接座標，然而這個解法 leetcode 無法接受，因為花太多時間。