泛洪算法-图像填充

适用级别:入门组
难度系数: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 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/**************************************************************** 
 * 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

Scroll to Top