Flood Fill Problem using recursion in Java

Hello Everyone! In this Java tutorial, we are going to discuss the problem of flood fill using ‘n’ no of ways. We are going to use the recursion method to solve this problem.

What is the Flood Fill Problem

First under what is the Flood fill problem, In the problem, we have given a maze we have S is the starting point and E ending point. In this problem, we have to start from S and go to E. Flood fill is an algorithm that mainly used to determine a bounded area connected to a given node in a multi-dimensional array. In these 0 marks, you can walk & 1 is the stop or change the direction.

  • We cannot intersect lines.
  • We cannot use the same path.

 

0  .S100000
0101110
0000000
1011011
1011011
1000000. E

Algorithm to solve Flood Fill problem in Java:-

  • Take the position of the starting point.
  • Decide whether you want to go in 4 directions (T=Top, L=Left, D=Down, R=Right).
  • Starting travel in those directions.

 

Java Code for solving flood fill problem

import java.util.*;

public class Main
{
    private static final Scanner sc= new Scanner(System.in);
    public static void main(String[] args) throws Exception {
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] arr = new int[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                arr[i][j] = sc.nextInt();
            }
        }

        sc.close();
        floodfill(arr, 0, 0, "", new boolean[n][m]);
    }

    public static void floodfill(int[][] maze, int row, int col, String psf, boolean[][] visited) {
        if (row < 0 || col < 0 || row >= maze.length || col >= maze[0].length
                || maze[row][col] == 1 || visited[row][col] == true) {
            return;
        } else if (row == maze.length - 1 && col == maze[0].length - 1) {
            System.out.println(psf);
            return;
        }

        visited[row][col] = true;
        floodfill(maze, row - 1, col, psf + "t", visited);
        floodfill(maze, row, col - 1, psf + "l", visited);
        floodfill(maze, row + 1, col, psf + "d", visited);
        floodfill(maze, row, col + 1, psf + "r", visited);
        visited[row][col] = false;
    }

}

Input

6 7
0 1 0 0 0 0 0
0 1 0 1 1 1 0
0 0 0 0 0 0 0
1 0 1 1 0 1 1
1 0 1 1 0 1 1
1 0 0 0 0 0 0

Output

ddrdddrrrrr
ddrrttrrrrddlldddrr
ddrrrrdddrr

N0w, You can understand there is minimal path 3 paths Start to the endpoint.

Leave a Reply

Your email address will not be published. Required fields are marked *