Last active
March 1, 2022 15:50
-
-
Save VarunVats9/14c08797c6fd7b827ce2b2f9dfa8db5e to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.HashSet; | |
import java.util.Objects; | |
import java.util.Set; | |
import java.util.Stack; | |
public class FloodFill { | |
private static final String SEPARATOR = "--------------------------------------------------------------------"; | |
private static final int[][] directions = new int[][]{ | |
{0, 1}, | |
{1, 0}, | |
{0, -1}, | |
{-1, 0}}; | |
public static void main(String[] args) { | |
// Setup the matrix. | |
int[][] matrix = new int[][]{ | |
{1, 1, 1, 1, 1, 1}, | |
{1, 1, 2, 2, 1, 1}, | |
{1, 1, 2, 2, 1, 1}, | |
{2, 2, 2, 2, 2, 2}}; | |
// Approach 1 : Using STACK. | |
{ | |
System.out.println("************** STACK APPROACH ************* \n"); | |
final long stackApproachStart = System.nanoTime(); | |
Stack<Pair> stack = new Stack<>(); | |
Set<Pair> visited = new HashSet<>(); | |
// Starting point. | |
Pair start = new Pair(2, 2); | |
stack.add(start); | |
while (!stack.isEmpty()) { | |
Pair pair = stack.pop(); | |
if (matrix[pair.row][pair.col] == 3) { | |
continue; | |
} | |
for (int i = 0; i < directions.length; i++) { | |
int x = pair.row + directions[i][0]; | |
int y = pair.col + directions[i][1]; | |
if (x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length || matrix[x][y] != 2 || visited.contains(new Pair(x, y))) { | |
continue; | |
} | |
stack.add(new Pair(x, y)); | |
} | |
visited.add(pair); | |
matrix[pair.row][pair.col] = 3; | |
} | |
printMatrix(matrix); | |
System.out.println("\nTotal time taken by STACK approach : [" + (System.nanoTime() - stackApproachStart) / 1000 + "] us\n"); | |
} | |
System.out.println(SEPARATOR); | |
// Approach 2 : Using DFS. | |
{ | |
System.out.println("\n************** DFS APPROACH ************* \n"); | |
final long dfsApproachStart = System.nanoTime(); | |
Set<Pair> visited = new HashSet<>(); | |
// Starting point. | |
Pair start = new Pair(2, 2); | |
dfsOnMatrix(start, matrix, visited); | |
printMatrix(matrix); | |
System.out.println("\nTotal time taken by DFS approach : [" + (System.nanoTime() - dfsApproachStart) / 1000 + "] us"); | |
} | |
} | |
private static void dfsOnMatrix(final Pair pair, final int[][] matrix, final Set<Pair> visited) { | |
if (matrix[pair.row][pair.col] == 3) { | |
return; | |
} | |
for (int i = 0; i < directions.length; i++) { | |
int x = pair.row + directions[i][0]; | |
int y = pair.col + directions[i][1]; | |
if (x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length || matrix[x][y] != 2 || visited.contains(new Pair(x, y))) { | |
continue; | |
} | |
dfsOnMatrix(new Pair(x, y), matrix, visited); | |
} | |
visited.add(pair); | |
matrix[pair.row][pair.col] = 3; | |
} | |
private static void printMatrix(final int[][] matrix) { | |
for (int i = 0; i < matrix.length; i++) { | |
for (int j = 0; j < matrix[0].length; j++) { | |
System.out.print(matrix[i][j] + ","); | |
} | |
System.out.println(); | |
} | |
} | |
private static class Pair { | |
private int row; | |
private int col; | |
public Pair(final int row, final int col) { | |
this.row = row; | |
this.col = col; | |
} | |
@Override | |
public boolean equals(final Object o) { | |
if (this == o) return true; | |
if (o == null || getClass() != o.getClass()) return false; | |
final Pair pair = (Pair)o; | |
return row == pair.row && | |
col == pair.col; | |
} | |
@Override | |
public int hashCode() { | |
return Objects.hash(row, col); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Try this!
private static void dfsOnMatrix(final Pair pair, final int[][] matrix, final Set visited) {