flood_fill

공략법

전형적인 DFS 문제

flood_fill() 에서 주어진 begin의 값을 찾는다

void    flood_fill(char **tab, t_point size, t_point begin)
{
    fill(tab, size, begin, tab[begin.x][begin.y]);
}

이후 fill()이라는 함수를 만든다.

구조체는 다음과 같이 만들 수 있다 : (t_type){point.x, point.y}

void    fill(char **tab, t_point size, t_point cur, char base)
{
    if (cur.x < 0 || cur.x > size.x)
        return ;
    if (cur.y < 0 || cur.y > size.y)
        return ;
    if (tab[cur.x][cur.y] != base)
        return ;

    tab[cur.x][cur.y] = 'F';

    flood_fill(tab, size, (t_point){cur.x + 1, cur.y});
    flood_fill(tab, size, (t_point){cur.x, cur.y + 1});
    flood_fill(tab, size, (t_point){cur.x - 1, cur.y});
    flood_fill(tab, size, (t_point){cur.x, cur.y - 1});
}

문제

Assignment name  : flood_fill
Expected files   : *.c, *.h
Allowed functions: -
--------------------------------------------------------------------------------

Write a function that takes a char ** as a 2-dimensional array of char, a
t_point as the dimensions of this array and a t_point as the starting point.

Starting from the given 'begin' t_point, this function fills an entire zone
by replacing characters inside with the character 'F'. A zone is an group of
the same character delimitated horizontally and vertically by other characters
or the array boundry.

The flood_fill function won't fill diagonally.

The flood_fill function will be prototyped like this:
  void  flood_fill(char **tab, t_point size, t_point begin);

The t_point structure is prototyped like this:

  typedef struct  s_point
  {
    int           x;
    int           y;
  }               t_point;

Example:

$> cat test.c
#include <stdlib.h>
#include <stdio.h>
#include "flood_fill.h"

char** make_area(char** zone, t_point size)
{
	char** new;

	new = malloc(sizeof(char*) * size.y);
	for (int i = 0; i < size.y; ++i)
	{
		new[i] = malloc(size.x + 1);
		for (int j = 0; j < size.x; ++j)
			new[i][j] = zone[i][j];
		new[i][size.x] = '\0';
	}

	return new;
}

int main(void)
{
	t_point size = {8, 5};
	char *zone[] = {
		"11111111",
		"10001001",
		"10010001",
		"10110001",
		"11100001",
	};

	char**  area = make_area(zone, size);
	for (int i = 0; i < size.y; ++i)
		printf("%s\n", area[i]);
	printf("\n");

	t_point begin = {7, 4};
	flood_fill(area, size, begin);
	for (int i = 0; i < size.y; ++i)
		printf("%s\n", area[i]);
	return (0);
}

$> gcc flood_fill.c test.c -o test; ./test
11111111
10001001
10010001
10110001
11100001

FFFFFFFF
F000F00F
F00F000F
F0FF000F
FFF0000F
$>