Fix bound checks in flood fill (fixes TheAlgorithms#2836) (TheAlgorithms#2974)

nikslyon19 · web-flow · commit 260a302563c5 · 2022-03-12T11:56:43.000+02:00
diff --git a/src/main/java/com/thealgorithms/backtracking/FloodFill.java 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);
+
+	}
+
+}
diff --git a/src/main/java/com/thealgorithms/dynamicprogramming/FloodFill.java b/src/main/java/com/thealgorithms/dynamicprogramming/FloodFill.java
diff --git a/src/test/java/com/thealgorithms/backtracking/FloodFillTest.java 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);
+    }
+
+}
