泛洪算法-图像填充

适用级别：入门组
难度系数：5

图像填充算法，又称泛洪算法——Flood Fill（也称为种子填充——Seed Fill），用于确定连接到多维数组中给定节点的区域。例如在做图软件中，填充颜色相似的区域，或者在诸如围棋（Go）和扫雷（Minesweeper）之类的游戏中用于确定哪些块被清除。泛洪算法的基本原理就是从一个像素点出发，以此向周边的像素点扩充着色，直到图形的边界。

给定一个两维数组arr[][]来表示平面图像，每个arr[i][j]都用整数代表一个像素的颜色，现在给定一个像素的位置pixel(x,y)和颜色c，用给定的颜色替换所有与pixel(x,y)相邻的同颜色像素点。

Input: arr[][] = { 
{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, C = 3

output:
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

/**************************************************************** 
 * Description: C++ implementation of Flood Fill
 * Author: Alex Li
 * Date: 2023-06-14 10:57:04
 * LastEditTime: 2023-06-14 11:22:29
****************************************************************/

#include <iostream>
using namespace std;

//Floodfill function
void FloodFill(int screen[8][8],int sr,int sc,int row, int column, int prevC, int newC){
     // Condition for checking out of bounds
    if (sr < 0 || sr >= row || sc < 0 || sc >= column) return;
    if (screen[sr][sc] != prevC)return;
     screen[sr][sc] = newC;
    FloodFill(screen, sr - 1, sc, row, column, prevC, newC); // left
    FloodFill(screen, sr + 1, sc, row, column, prevC, newC); // right
    FloodFill(screen, sr, sc + 1, row, column, prevC, newC); // top
    FloodFill(screen, sr, sc - 1, row, column, prevC, newC); // bottom
}

int main(){
    int screen[8][8]=
            { 
            { 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, 2, 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, 2, 2, 2, 1 }
            };
           // Row of the display
          int row=8;
          // Column of the display
          int column=8;
          // Co-ordinate provided by the user
          int x=4;
          int y=4;
          // Current color at that co-ordinate
          int prevColor=screen[x][y];
          // New color will be filled
          int newColor=3;

          FloodFill(screen, x, y, row, column, prevColor, newColor);

          // Printing the updated screen
        for (int i = 0; i < row; i++) {
        for (int j = 0; j < column; j++) {
            cout << screen[i][j] << " ";
        }
        cout << endl;
    }
return 0;

}

洛谷：P1162 P1745

P1162-1

Previous Topic

Back to Lesson

Next Topic

数据结构与算法

泛洪算法-图像填充