FloodFill算法詳解及應用

啥是 FloodFill 算法呢，

最直接的一個應用就是「顏色填充」，就是 Windows 繪畫本中那個小油漆桶的標志，可以把一塊被圈起來的區域全部染色。 這種算法思想還在許多其他地方有應用。比如說掃雷游戲，有時候你點一個方格，會一下子展開一片區域，這個展開過程，就是 FloodFill 算法實現的。 類似的，像消消樂這類游戲，相同方塊積累到一定數量，就全部消除，也是 FloodFill 算法的功勞。

一、構建框架

以上幾個例子，都可以抽象成一個二維矩陣，然后從某個點開始向四周擴展，直到無法再擴展為止。

矩陣，可以抽象為一幅「圖」，這就是一個圖的遍歷問題，也就類似一個 N 叉樹遍歷的問題。幾行代碼就能解決，直接上框架吧：

// (x, y) 為坐標位置 void fill(int x, int y) {fill(x - 1, y); // 上fill(x + 1, y); // 下fill(x, y - 1); // 左fill(x, y + 1); // 右 }

這個框架可以解決所有在二維矩陣中遍歷的問題，說得高端一點，這就叫深度優先搜索（Depth First Search，簡稱 DFS），說得簡單一點，這就叫四叉樹遍歷框架。坐標 (x, y) 就是 root，四個方向就是 root 的四個子節點。

看一道題：

有了框架，直接上代碼：

int[][] floodFill(int[][] image,int sr, int sc, int newColor) {int origColor = image[sr][sc];fill(image, sr, sc, origColor, newColor);return image; }void fill(int[][] image, int x, int y,int origColor, int newColor) {// 出界：超出邊界索引if (!inArea(image, x, y)) return;// 碰壁：遇到其他顏色，超出 origColor 區域if (image[x][y] != origColor) return;image[x][y] = newColor;fill(image, x, y + 1, origColor, newColor);fill(image, x, y - 1, origColor, newColor);fill(image, x - 1, y, origColor, newColor);fill(image, x + 1, y, origColor, newColor); }boolean inArea(int[][] image, int x, int y) {return x >= 0 && x < image.length&& y >= 0 && y < image[0].length; }

此算法已經 cover 了 99% 的情況，僅有一個細節問題沒有解決，就是當 origColor 和 newColor 相同時，會陷入無限遞歸

二、研究細節

為什么會陷入無限遞歸呢，很好理解，因為每個坐標都要搜索上下左右，那么對于一個坐標，一定會被上下左右的坐標搜索。被重復搜索時，必須保證遞歸函數能夠能正確地退出，否則就會陷入死循環。

為什么 newColor 和 origColor 不同時可以正常退出呢？把算法流程畫個圖理解一下：

可以看到，fill(1, 1) 被重復搜索了，我們用 fill(1, 1)* 表示這次重復搜索。fill(1, 1)* 執行時，(1, 1) 已經被換成了 newColor，所以 fill(1, 1)* 會在這個 if 語句被懟回去，正確退出了。

// 碰壁：遇到其他顏色，超出 origColor 區域 if (image[x][y] != origColor) return;

但是，如果說 origColor 和 newColor 一樣，這個 if 語句就無法讓 fill(1, 1)* 正確退出，而是開啟了下面的重復遞歸，形成了死循環。

三、處理細節

如何避免上述問題的發生，最容易想到的就是用一個和 image 一樣大小的二維 bool 數組記錄走過的地方，一旦發現重復立即 return。

// 出界：超出邊界索引 if (!inArea(image, x, y)) return; // 碰壁：遇到其他顏色，超出 origColor 區域 if (image[x][y] != origColor) return;// 不走回頭路 if (visited[x][y]) return;visited[x][y] = true; image[x][y] = newColor;

完全 OK，這也是處理「圖」的一種常用手段。不過對于此題，不用開數組，我們有一種更好的方法，那就是回溯算法。

前文「回溯算法詳解」講過，這里不再贅述，直接套回溯算法框架：

void fill(int[][] image, int x, int y,int origColor, int newColor) {// 出界：超出數組邊界if (!inArea(image, x, y)) return;// 碰壁：遇到其他顏色，超出 origColor 區域if (image[x][y] != origColor) return;// 已探索過的 origColor 區域if (image[x][y] == -1) return;// choose：打標記，以免重復image[x][y] = -1;fill(image, x, y + 1, origColor, newColor);fill(image, x, y - 1, origColor, newColor);fill(image, x - 1, y, origColor, newColor);fill(image, x + 1, y, origColor, newColor);// unchoose：將標記替換為 newColorimage[x][y] = newColor; }

這種解決方法是最常用的，相當于使用一個特殊值 -1 代替 visited 數組的作用，達到不走回頭路的效果。為什么是 -1，因為題目中說了顏色取值在 0 - 65535 之間，所以 -1 足夠特殊，能和顏色區分開

四、自動魔棒工具和掃雷中FloodFill算法的應用

大部分圖片編輯軟件一定有「自動魔棒工具」這個功能：點擊一個地方，幫你自動選中相近顏色的部分。如下圖，我想選中老鷹，可以先用自動魔棒選中藍天背景，然后反向選擇，就選中了老鷹。我們來分析一下自動魔棒工具的原理。

顯然，這個算法肯定是基于 FloodFill 算法的，但有兩點不同：

首先，背景色是藍色，但不能保證都是相同的藍色，畢竟是像素點，可能存在肉眼無法分辨的深淺差異，而我們希望能夠忽略這種細微差異。

第二，FloodFill 算法是「區域填充」，這里更像「邊界填充」。

對于第一個問題，很好解決，可以設置一個閾值 threshold，在閾值范圍內波動的顏色都視為 origColor：

if (Math.abs(image[x][y] - origColor) > threshold)return;

對于第二個問題，我們首先明確問題：不要把區域內所有 origColor 的都染色，而是只給區域最外圈染色。然后，我們分析，如何才能僅給外圍染色，即如何才能找到最外圍坐標，最外圍坐標有什么特點？

可以發現，區域邊界上的坐標，至少有一個方向不是 origColor，而區域內部的坐標，四面都是 origColor，這就是解決問題的關鍵。保持框架不變，使用 visited 數組記錄已搜索坐標，主要代碼如下：

int fill(int[][] image, int x, int y,int origColor, int newColor) {// 出界：超出數組邊界if (!inArea(image, x, y)) return 0;// 已探索過的 origColor 區域if (visited[x][y]) return 1;// 碰壁：遇到其他顏色，超出 origColor 區域if (image[x][y] != origColor) return 0;visited[x][y] = true;int surround = fill(image, x - 1, y, origColor, newColor)+ fill(image, x + 1, y, origColor, newColor)+ fill(image, x, y - 1, origColor, newColor)+ fill(image, x, y + 1, origColor, newColor);if (surround < 4)image[x][y] = newColor;return 1; }

這樣，區域內部的坐標探索四周后得到的 surround 是 4，而邊界的坐標會遇到其他顏色，或超出邊界索引，surround 會小于 4。如果你對這句話不理解，我們把邏輯框架抽象出來看：

int fill(int[][] image, int x, int y,int origColor, int newColor) {// 出界：超出數組邊界if (!inArea(image, x, y)) return 0;// 已探索過的 origColor 區域if (visited[x][y]) return 1;// 碰壁：遇到其他顏色，超出 origColor 區域if (image[x][y] != origColor) return 0;// 未探索且屬于 origColor 區域if (image[x][y] == origColor) {// ...return 1;} }

這 4 個 if 判斷涵蓋了 (x, y) 的所有可能情況，surround 的值由四個遞歸函數相加得到，而每個遞歸函數的返回值就這四種情況的一種。借助這個邏輯框架，你一定能理解上面那句話了。

這樣就實現了僅對 origColor 區域邊界坐標染色的目的，等同于完成了魔棒工具選定區域邊界的功能。

這個算法有兩個細節問題，一是必須借助 visited 來記錄已探索的坐標，而無法使用回溯算法；二是開頭幾個 if 順序不可打亂。

同理，思考掃雷游戲，應用 FloodFill 算法展開空白區域的同時，也需要計算并顯示邊界上雷的個數，如何實現的？

其實也是相同的思路，遇到雷就返回 true，這樣 surround 變量存儲的就是雷的個數。當然，掃雷的 FloodFill 算法不能只檢查上下左右，還得加上四個斜向。

總結

以上是生活随笔為你收集整理的FloodFill算法详解及应用的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。