# 洪水填充算法–如何在 paint 中實現 fill（）？ > 原文： [https://www.geeksforgeeks.org/flood-fill-algorithm-implement-fill-paint/](https://www.geeksforgeeks.org/flood-fill-algorithm-implement-fill-paint/) 在 MS-Paint 中，當我們將畫筆帶到一個像素并單擊時，該像素區域的顏色將替換為新的選定顏色。 以下是執行此任務的問題說明。 給定 2D 屏幕，屏幕中像素的位置和顏色，用給定顏色替換給定像素和所有相鄰的相同彩色像素的顏色。 **示例**： ``` Input: screen[M][N] = {{1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 0, 0}, {1, 0, 0, 1, 1, 0, 1, 1}, {1, 2, 2, 2, 2, 0, 1, 0}, {1, 1, 1, 2, 2, 0, 1, 0}, {1, 1, 1, 2, 2, 2, 2, 0}, {1, 1, 1, 1, 1, 2, 1, 1}, {1, 1, 1, 1, 1, 2, 2, 1}, }; x = 4, y = 4, newColor = 3 The values in the given 2D screen indicate colors of the pixels. x and y are coordinates of the brush, newColor is the color that should replace the previous color on screen[x][y] and all surrounding pixels with same color. Output: Screen should be changed to following. screen[M][N] = {{1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 0, 0}, {1, 0, 0, 1, 1, 0, 1, 1}, {1, 3, 3, 3, 3, 0, 1, 0}, {1, 1, 1, 3, 3, 0, 1, 0}, {1, 1, 1, 3, 3, 3, 3, 0}, {1, 1, 1, 1, 1, 3, 1, 1}, {1, 1, 1, 1, 1, 3, 3, 1}, }; ``` [**洪水填充算法**：](http://en.wikipedia.org/wiki/Flood_fill) 這個想法很簡單，我們首先替換當前像素的顏色，然后對 4 個周圍的點進行遞歸。 以下是詳細的算法。 ``` // A recursive function to replace previous color 'prevC' at '(x, y)' // and all surrounding pixels of (x, y) with new color 'newC' and floodFil(screen[M][N], x, y, prevC, newC) 1) If x or y is outside the screen, then return. 2) If color of screen[x][y] is not same as prevC, then return 3) Recur for north, south, east and west. floodFillUtil(screen, x+1, y, prevC, newC); floodFillUtil(screen, x-1, y, prevC, newC); floodFillUtil(screen, x, y+1, prevC, newC); floodFillUtil(screen, x, y-1, prevC, newC); ``` 以下是上述算法的實現。 ## C++ ```cpp // A C++ program to implement flood fill algorithm #include<iostream> using namespace std; // Dimentions of paint screen #define M 8 #define N 8 // A recursive function to replace previous color 'prevC' at? '(x, y)'? // and all surrounding pixels of (x, y) with new color 'newC' and void floodFillUtil(int screen[][N], int x, int y, int prevC, int newC) { ????// Base cases ????if (x < 0 || x >= M || y < 0 || y >= N) ????????return; ????if (screen[x][y] != prevC) ????????return; ????if (screen[x][y] == newC)? ????????return;? ????// Replace the color at (x, y) ????screen[x][y] = newC; ????// Recur for north, east, south and west ????floodFillUtil(screen, x+1, y, prevC, newC); ????floodFillUtil(screen, x-1, y, prevC, newC); ????floodFillUtil(screen, x, y+1, prevC, newC); ????floodFillUtil(screen, x, y-1, prevC, newC); } // It mainly finds the previous color on (x, y) and // calls floodFillUtil() void floodFill(int screen[][N], int x, int y, int newC) { ????int prevC = screen[x][y]; ????floodFillUtil(screen, x, y, prevC, newC); } // Driver program to test above function int main() { ????int screen[M][N] = {{1, 1, 1, 1, 1, 1, 1, 1}, ??????????????????????{1, 1, 1, 1, 1, 1, 0, 0}, ??????????????????????{1, 0, 0, 1, 1, 0, 1, 1}, ??????????????????????{1, 2, 2, 2, 2, 0, 1, 0}, ??????????????????????{1, 1, 1, 2, 2, 0, 1, 0}, ??????????????????????{1, 1, 1, 2, 2, 2, 2, 0}, ??????????????????????{1, 1, 1, 1, 1, 2, 1, 1}, ??????????????????????{1, 1, 1, 1, 1, 2, 2, 1}, ?????????????????????}; ????int x = 4, y = 4, newC = 3; ????floodFill(screen, x, y, newC); ????cout << "Updated screen after call to floodFill: \n"; ????for (int i=0; i<M; i++) ????{ ????????for (int j=0; j<N; j++) ???????????cout << screen[i][j] << " "; ????????cout << endl; ????} } ```