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  .S	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. 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.

One response to “Flood Fill Problem using recursion in Java”

1. Mike Goldstein says:

   June 3, 2022 at 6:50 pm

   Thank you, I have been having a hard time with my MIT assignment. This was incredibly helpful you beautiful human being from heaven. We strive to have more people like you in this world.

   Reply