Java Program to Implement Flood Fill Algorithm

«
»
This is a Java Program to Implement Flood Fill Algorithm. Flood fill, also called seed fill, is an algorithm that determines the area connected to a given node in a multi-dimensional array. It is used in the “bucket” fill tool of paint programs to fill connected, similarly-colored areas with a different color, and in games such as Go and Minesweeper for determining which pieces are cleared. When applied on an image to fill a particular bounded area with color, it is also known as boundary fill. Here ‘P’ is for passage, ‘O’ for obstacle and ‘W’ for water flow.

Here is the source code of the Java Program to Implement Flood Fill Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. /**
  2.  * Java Program to Implement Flood Fill Algorithm
  3.  **/
  4.  
  5. import java.util.Scanner;
  6. import java.util.Arrays;
  7.  
  8. /** Class FloodFill **/
  9. public class FloodFill
  10. {
  11.     /** Function to fill grid **/
  12.     private void fillGrid(char[][] arr, int r, int c) 
  13.     {
  14.         if (arr[r][c] == 'P')
  15.         {
  16.             arr[r][c] = 'W';
  17.             display(arr);
  18.  
  19.             fillGrid(arr, r + 1, c);
  20.             fillGrid(arr, r - 1, c);
  21.             fillGrid(arr, r, c + 1);
  22.             fillGrid(arr, r, c - 1);
  23.         }
  24.     }
  25.     /** Function to display grid **/
  26.     private void display(char[][] arr)
  27.     {
  28.         System.out.println("\nGrid : ");
  29.         for (int i = 1; i < arr.length - 1; i++)
  30.         {
  31.             for (int j = 1; j < arr[i].length - 1; j++)
  32.                 System.out.print(arr[i][j] +" ");
  33.             System.out.println();
  34.         }
  35.     }
  36.  
  37.     /** Main method **/
  38.     public static void main(String[] args) 
  39.     {
  40.         Scanner scan = new Scanner( System.in );        
  41.         System.out.println("Flood Fill Test\n");
  42.  
  43.         /** Accept dimensions **/
  44.         System.out.println("Enter dimensions of grid");
  45.         int M = scan.nextInt();
  46.         int N = scan.nextInt();
  47.  
  48.         /** make grid with border as obstacle to avoid boundary conditions **/
  49.         char[][] arr = new char[M + 2][N + 2];
  50.         for (int i = 0; i < M + 2; i++)
  51.             Arrays.fill(arr[i], 'O');
  52.  
  53.         /** Accept grid **/
  54.         System.out.println("Enter grid with 'P' for passage and 'O' for obstacle");
  55.  
  56.         for (int i = 1; i < M + 1; i++)
  57.             for (int j = 1; j < N + 1; j++)
  58.                 arr[i][j] = scan.next().charAt(0);    
  59.  
  60.         System.out.println("Enter coordinates to start ");
  61.         int sr = scan.nextInt();
  62.         int sc = scan.nextInt();
  63.  
  64.         if (arr[sr][sc] != 'P')
  65.         {
  66.             System.out.println("Invalid coordinates");
  67.             System.exit(0);
  68.         }
  69.  
  70.         FloodFill ff = new FloodFill();
  71.         ff.fillGrid(arr, sr, sc);    
  72.  
  73.     }    
  74. }

advertisement
Flood Fill Test
 
Enter dimensions of grid
5 5
Enter grid with 'P' for passage and 'O' for obstacle
P P P P P
O P O P O
O O P P O
P P P O O
P O O O O
Enter coordinates to start
3 3
 
Grid :
P P P P P
O P O P O
O O W P O
P P P O O
P O O O O
 
Grid :
P P P P P
O P O P O
O O W P O
P P W O O
P O O O O
 
Grid :
P P P P P
O P O P O
O O W P O
P W W O O
P O O O O
 
Grid :
P P P P P
O P O P O
O O W P O
W W W O O
P O O O O
 
Grid :
P P P P P
O P O P O
O O W P O
W W W O O
W O O O O
 
Grid :
P P P P P
O P O P O
O O W W O
W W W O O
W O O O O
 
Grid :
P P P P P
O P O W O
O O W W O
W W W O O
W O O O O
 
Grid :
P P P W P
O P O W O
O O W W O
W W W O O
W O O O O
 
Grid :
P P P W W
O P O W O
O O W W O
W W W O O
W O O O O
 
Grid :
P P W W W
O P O W O
O O W W O
W W W O O
W O O O O
 
Grid :
P W W W W
O P O W O
O O W W O
W W W O O
W O O O O
 
Grid :
P W W W W
O W O W O
O O W W O
W W W O O
W O O O O
 
Grid :
W W W W W
O W O W O
O O W W O
W W W O O
W O O O O

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.