Skip to content

Fixes: #2836 #2974

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 3 commits into from
Mar 12, 2022
Merged

Fixes: #2836 #2974

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
3 commits
Select commit Hold shift + click to select a range
06416d4
Fixes for FloodFill Algorithm (#2836)
nikslyon19 Mar 9, 2022
ca0cf40
Merge branch 'TheAlgorithms:master' into master
nikslyon19 Mar 11, 2022
d0c00fe
Implemented suggested changes (#2836)
nikslyon19 Mar 11, 2022
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
69 changes: 69 additions & 0 deletions src/main/java/com/thealgorithms/backtracking/FloodFill.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,69 @@
package com.thealgorithms.backtracking;

/**
* Java program for Flood fill algorithm.
* @author Akshay Dubey (https://github.com/itsAkshayDubey)
*/
public class FloodFill {

/**
* Get the color at the given co-odrinates of a 2D image
*
* @param image The image to be filled
* @param x The x co-ordinate of which color is to be obtained
* @param y The y co-ordinate of which color is to be obtained
*/

public static int getPixel(int[][] image, int x, int y) {

return image[x][y];

}

/**
* Put the color at the given co-odrinates of a 2D image
*
* @param image The image to be filed
* @param x The x co-ordinate at which color is to be filled
* @param y The y co-ordinate at which color is to be filled
*/
public static void putPixel(int[][] image, int x, int y, int newColor) {

image[x][y] = newColor;

}


/**
* Fill the 2D image with new color
*
* @param image The image to be filed
* @param x The x co-ordinate at which color is to be filled
* @param y The y co-ordinate at which color is to be filled
* @param newColor The new color which to be filled in the image
* @param oldColor The old color which is to be replaced in the image
* @return
*/
public static void floodFill(int[][] image, int x, int y, int newColor, int oldColor) {

if(x < 0 || x >= image.length) return;
if(y < 0 || y >= image[x].length) return;
if(getPixel(image, x, y) != oldColor) return;

putPixel(image, x, y, newColor);

/* Recursively check for horizontally & vertically adjacent coordinates */
floodFill(image, x + 1, y, newColor, oldColor);
floodFill(image, x - 1, y, newColor, oldColor);
floodFill(image, x, y + 1, newColor, oldColor);
floodFill(image, x, y - 1, newColor, oldColor);

/* Recursively check for diagonally adjacent coordinates */
floodFill(image, x + 1, y - 1, newColor, oldColor);
floodFill(image, x - 1, y + 1, newColor, oldColor);
floodFill(image, x + 1, y + 1, newColor, oldColor);
floodFill(image, x - 1, y - 1, newColor, oldColor);

}

}
114 changes: 0 additions & 114 deletions src/main/java/com/thealgorithms/dynamicprogramming/FloodFill.java
View file
Open in desktop

This file was deleted.

106 changes: 106 additions & 0 deletions src/test/java/com/thealgorithms/backtracking/FloodFillTest.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,106 @@
package com.thealgorithms.backtracking;

import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertArrayEquals;

class FloodFillTest {

@Test
void testForEmptyImage()
{
int image[][] = {};
int expected[][] = {};

FloodFill.floodFill(image, 4, 5, 3, 2);
assertArrayEquals(expected, image);
}


@Test
void testForSingleElementImage()
{
int image[][] = {{1}};
int expected[][] = {{3}};

FloodFill.floodFill(image, 0, 0, 3, 1);
assertArrayEquals(expected, image);
}


@Test
void testForImageOne()
{
int image[][] = {
{ 0,0,0,0,0,0,0 },
{ 0,3,3,3,3,0,0 },
{ 0,3,1,1,5,0,0 },
{ 0,3,1,1,5,5,3 },
{ 0,3,5,5,1,1,3 },
{ 0,0,0,5,1,1,3 },
{ 0,0,0,3,3,3,3 }
};

int expected[][] = {
{ 0,0,0,0,0,0,0 },
{ 0,3,3,3,3,0,0 },
{ 0,3,2,2,5,0,0 },
{ 0,3,2,2,5,5,3 },
{ 0,3,5,5,2,2,3 },
{ 0,0,0,5,2,2,3 },
{ 0,0,0,3,3,3,3 }
};

FloodFill.floodFill(image,2,2,2,1);
assertArrayEquals(expected, image);
}


@Test
void testForImageTwo()
{
int image[][] = {
{ 0,0,1,1,0,0,0 },
{ 1,1,3,3,3,0,0 },
{ 1,3,1,1,5,0,0 },
{ 0,3,1,1,5,5,3 },
{ 0,3,5,5,1,1,3 },
{ 0,0,0,5,1,1,3 },
{ 0,0,0,1,3,1,3 }
};

int expected[][] = {
{ 0,0,2,2,0,0,0 },
{ 2,2,3,3,3,0,0 },
{ 2,3,2,2,5,0,0 },
{ 0,3,2,2,5,5,3 },
{ 0,3,5,5,2,2,3 },
{ 0,0,0,5,2,2,3 },
{ 0,0,0,2,3,2,3 }
};

FloodFill.floodFill(image, 2, 2, 2, 1);
assertArrayEquals(expected, image);
}


@Test
void testForImageThree()
{
int image[][] = {
{ 1,1,2,3,1,1,1 },
{ 1,0,0,1,0,0,1 },
{ 1,1,1,0,3,1,2 }
};

int expected[][] = {
{ 4,4,2,3,4,4,4 },
{ 4,0,0,4,0,0,4 },
{ 4,4,4,0,3,4,2 },
};

FloodFill.floodFill(image, 0, 1, 4, 1);
assertArrayEquals(expected, image);
}

}