flood_fill

# flood_fill

## Conceptual Overview
### The Problem
We are asked to write a function that takes arguments of a 2-dimensional array of chars and two coordinate pairs representing the dimensions of the array and the starting point in the array, respectively. The function replaces the starting character and all "connected" characters with 'F', where connected characters are those that have the same value as the starting character and are one space above, below, to the left, or to the right of the starting character or another connected character.

<details>
	<summary>Full Subject</summary>

```
	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
	$> 
```
</details>

### References
* [Subject File (English)](subject.en.txt)
* [flood_fill.c](flood_fill.c)

### Approach

Save the value of the character at the starting location. For each location beginning with the starting position, check if the current location is in-bounds and if the character at the current location matches the character originally at the starting location. If so, change the character at the current location to 'F' and repeat with the locations one row above, one row below, one column to the left, and one column to the right.

### Code
```C
// This code is heavily influenced by @jochang's solution: github.com/MagicHatJo

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

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

	tab[cur.y][cur.x] = 'F';
	fill(tab, size, (t_point){cur.x - 1, cur.y}, to_fill);
	fill(tab, size, (t_point){cur.x + 1, cur.y}, to_fill);
	fill(tab, size, (t_point){cur.x, cur.y - 1}, to_fill);
	fill(tab, size, (t_point){cur.x, cur.y + 1}, to_fill);
}

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

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
$> 

------------------------------------------------------------------------

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

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

	tab[cur.y][cur.x] = 'F';
	fill(tab, size, (t_point){cur.x - 1, cur.y}, to_fill);
	fill(tab, size, (t_point){cur.x + 1, cur.y}, to_fill);
	fill(tab, size, (t_point){cur.x, cur.y - 1}, to_fill);
	fill(tab, size, (t_point){cur.x, cur.y + 1}, to_fill);
}

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