Repository: TheAlgorithms/Java
Pull request #2974 (2022-03-09 03:43:22)

Fixes: #2836
### **Describe your change:**

- [x] Fix a bug or typo in an existing algorithm?

#### References

<!-- Add any reference to previous pull-request or issue -->

Issue No. #2836


### **Checklist:**

<!-- Remove items that do not apply. For completed items, change [ ] to [x]. -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized.
- [x] I know that pull requests will not be merged if they fail the automated tests.
- [x] This PR only changes one algorithm file. To ease review, please open separate PRs for separate algorithms.
- [x] All new Java files are placed inside an existing directory.
- [x] All filenames are in all uppercase characters with no spaces or dashes.
- [x] If this pull request resolves one or more open issues then the commit message contains `Fixes: #{$ISSUE_NO}`.



Patch:
diff --git a/src/main/java/com/thealgorithms/backtracking/FloodFill.java b/src/main/java/com/thealgorithms/backtracking/FloodFill.java
new file mode 100644
index 00000000..d7842a67
--- /dev/null
+++ b/src/main/java/com/thealgorithms/backtracking/FloodFill.java
@@ -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);
+
+	}
+
+}
\ No newline at end of file
diff --git a/src/main/java/com/thealgorithms/dynamicprogramming/FloodFill.java b/src/main/java/com/thealgorithms/dynamicprogramming/FloodFill.java
deleted file mode 100644
index 8b7bd088..00000000
--- a/src/main/java/com/thealgorithms/dynamicprogramming/FloodFill.java
+++ /dev/null
@@ -1,114 +0,0 @@
-package com.thealgorithms.dynamicprogramming;
-
-/**
- * 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_co_ordinate The x co-ordinate of which color is to be obtained
-     * @param y_co_ordinate The y co-ordinate of which color is to be obtained
-     */
-	
-	public static int getPixel(int[][] image, int x_co_ordinate, int y_co_ordinate) {
-	
-		return image[x_co_ordinate][y_co_ordinate];
-	
-	}
-	
-    /**
-     * Put the color at the given co-odrinates of a 2D image
-     *
-     * @param image The image to be filed
-     * @param x_co_ordinate The x co-ordinate at which color is to be filled
-     * @param y_co_ordinate The y co-ordinate at which color is to be filled
-     */
-	public static void putPixel(int[][] image, int x_co_ordinate, int y_co_ordinate, int new_color) {
-		
-		image[x_co_ordinate][y_co_ordinate] = new_color;
-	
-	}
-	
-	
-    /**
-     * Fill the 2D image with new color
-     *
-     * @param image The image to be filed
-     * @param x_co_ordinate The x co-ordinate at which color is to be filled
-     * @param y_co_ordinate The y co-ordinate at which color is to be filled
-     * @param new_color The new color which to be filled in the image
-     * @param old_color The old color which is to be replaced in the image
-     * @return
-     */
-	public static void floodFill(int[][] image, int x_co_ordinate, int y_co_ordinate, int new_color, int old_color) {
-		if(x_co_ordinate >= 0 && y_co_ordinate >= 0 && getPixel(image, x_co_ordinate, y_co_ordinate) == old_color) {
-			
-			putPixel(image, x_co_ordinate, y_co_ordinate, new_color);
-			floodFill(image, x_co_ordinate + 1, y_co_ordinate, new_color, old_color);
-			floodFill(image, x_co_ordinate - 1, y_co_ordinate, new_color, old_color);
-			floodFill(image, x_co_ordinate, y_co_ordinate + 1, new_color, old_color);
-			floodFill(image, x_co_ordinate, y_co_ordinate - 1, new_color, old_color);
-			floodFill(image, x_co_ordinate + 1, y_co_ordinate - 1, new_color, old_color);
-			floodFill(image, x_co_ordinate - 1, y_co_ordinate + 1, new_color, old_color);
-			floodFill(image, x_co_ordinate + 1, y_co_ordinate + 1, new_color, old_color);
-			floodFill(image, x_co_ordinate - 1, y_co_ordinate - 1, new_color, old_color);
-			
-			
-		}
-		
-	}
-	
-    /**
-     * This method will print the 2D image matrix
-     *
-     * @param image The image to be printed on the console
-     */
-	public static void printImageArray(int[][] image) {
-		
-		for(int i=0 ; i<image.length ; i++) {
-			for(int j=0 ; j<image[0].length ; j++) {
-				
-				System.out.print(image[i][j]+"  ");
-			}
-			
-			System.out.println();
-		}
-		
-	}
-	
-	// Driver Program
-	public static void main(String[] args) {
-		
-		
-		//Input 2D image matrix
-		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}
-		};
-		
-		floodFill(image,2,2,2,1);
-
-		/* Output ==>
-		 * 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
-		 * */
-		
-		//print 2D image matrix
-		printImageArray(image);
-	}
-
-}
\ No newline at end of file


Test patch:
diff --git a/src/test/java/com/thealgorithms/backtracking/FloodFillTest.java b/src/test/java/com/thealgorithms/backtracking/FloodFillTest.java
new file mode 100644
index 00000000..7b72e6b2
--- /dev/null
+++ b/src/test/java/com/thealgorithms/backtracking/FloodFillTest.java
@@ -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);
+    }
+
+}
\ No newline at end of file