Рубрики

Алгоритм заполнения Flood — как реализовать fill () в рисовании?

В 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},
                      };

Алгоритм заполнения потока:
Идея проста, мы сначала заменим цвет текущего пикселя, а затем повторить для 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 ++

// Программа на C ++ для реализации алгоритма заливки
#include<iostream>

using namespace std;

  
// Размеры краски экрана
#define M 8
#define N 8

  
// Рекурсивная функция для замены предыдущего цвета 'prevC' в '(x, y)'
// и все окружающие пиксели (x, y) с новым цветом 'newC' и

void floodFillUtil(int screen[][N], int x, int y, int prevC, int newC)

{

    // Базовые случаи

    if (x < 0 || x >= M || y < 0 || y >= N)

        return;

    if (screen[x][y] != prevC)

        return;

  

    // Заменить цвет на (x, y)

    screen[x][y] = newC;

  

    // Повторение на север, восток, юг и запад

    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);

}

  
// Он в основном находит предыдущий цвет на (x, y) и
// вызывает floodFillUtil ()

void floodFill(int screen[][N], int x, int y, int newC)

{

    int prevC = screen[x][y];

    floodFillUtil(screen, x, y, prevC, newC);

}

  
// Программа драйвера для проверки вышеуказанной функции

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;

    }

}

Джава

// Java-программа для реализации алгоритма заливки

class GFG

{

  
// Размеры краски экрана

static int M = 8;

static int N = 8;

  
// Рекурсивная функция для замены предыдущего цвета 'prevC' в '(x, y)'
// и все окружающие пиксели (x, y) с новым цветом 'newC' и

static void floodFillUtil(int screen[][], int x, int y, 

                                    int prevC, int newC)

{

    // Базовые случаи

    if (x < 0 || x >= M || y < 0 || y >= N)

        return;

    if (screen[x][y] != prevC)

        return;

  

    // Заменить цвет на (x, y)

    screen[x][y] = newC;

  

    // Повторение на север, восток, юг и запад

    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);

}

  
// Он в основном находит предыдущий цвет на (x, y) и
// вызывает floodFillUtil ()

static void floodFill(int screen[][], int x, int y, int newC)

{

    int prevC = screen[x][y];

    floodFillUtil(screen, x, y, prevC, newC);

}

  
// Код драйвера

public static void main(String[] args) 

{

    int screen[][] = {{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);

  

    System.out.println("Updated screen after call to floodFill: ");

    for (int i = 0; i < M; i++)

    {

        for (int j = 0; j < N; j++)

        System.out.print(screen[i][j] + " ");

        System.out.println();

    }

    }

}

  
// Этот код предоставлен 29AjayKumar

python3

# Python3 программа для реализации
# алгоритм заливки

  
# Размеры краски экрана

M = 8

N = 8

  
# Рекурсивная функция для замены
# предыдущий цвет 'prevC' в '(x, y)'
# и все окружающие пиксели (x, y)
# с новым цветом 'newC' и

def floodFillUtil(screen, x, y, prevC, newC):

      

    # Базовые случаи

    if (x < 0 or x >= M or y < 0 or 

        y >= N or screen[x][y] != prevC or 

        screen[x][y] == newC):

        return

  

    # Заменить цвет на (х, у)

    screen[x][y] = newC

  

    # Повтор для севера, востока, юга и запада

    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)

  
# Он в основном находит предыдущий цвет на (x, y) и
# вызывает floodFillUtil ()

def floodFill(screen, x, y, newC):

    prevC = screen[x][y]

    floodFillUtil(screen, x, y, prevC, newC)

  
Код водителя

screen = [[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

newC = 3

floodFill(screen, x, y, newC)

  

print ("Updated screen after call to floodFill:")

for i in range(M):

    for j in range(N):

        print(screen[i][j], end = ' ')

    print()

  
# Этот код предоставлен Ashutosh450

C #

// C # программа для реализации
// алгоритм заливки

using System; 

      

class GFG

{

  
// Размеры краски экрана

static int M = 8;

static int N = 8;

  
// Рекурсивная функция для замены
// предыдущий цвет 'prevC' в '(x, y)'
// и все окружающие пиксели (x, y)
// с новым цветом 'newC' и

static void floodFillUtil(int [,]screen, 

                          int x, int y, 

                          int prevC, int newC)

{

    // Базовые случаи

    if (x < 0 || x >= M || 

        y < 0 || y >= N)

        return;

    if (screen[x, y] != prevC)

        return;

  

    // Заменить цвет на (x, y)

    screen[x, y] = newC;

  

    // Повторение на север, восток, юг и запад

    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);

}

  
// В основном находит предыдущий цвет
// on (x, y) и вызывает floodFillUtil ()

static void floodFill(int [,]screen, int x,

                      int y, int newC)

{

    int prevC = screen[x, y];

    floodFillUtil(screen, x, y, prevC, newC);

}

  
// Код драйвера

public static void Main(String[] args) 

{

    int [,]screen = {{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);

  

    Console.WriteLine("Updated screen after"

                      "call to floodFill: ");

    for (int i = 0; i < M; i++)

    {

        for (int j = 0; j < N; j++)

        Console.Write(screen[i, j] + " ");

        Console.WriteLine();

    }

    }

}

  
// Этот код предоставлен PrinciRaj1992

Выход:

Updated screen after call to floodFill:
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

Эта статья предоставлена Anmol . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Алгоритм заполнения Flood — как реализовать fill () в рисовании?

0.00 (0%) 0 votes