|
|
/*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.*/
|
|
|
|
|
|
/**
|
|
|
* Java Program to Implement Flood Fill Algorithm
|
|
|
**/
|
|
|
|
|
|
import java.util.Scanner;
|
|
|
import java.util.Arrays;
|
|
|
|
|
|
/** Class FloodFill **/
|
|
|
public class FloodFill
|
|
|
{
|
|
|
/** Function to fill grid **/
|
|
|
private void fillGrid(char[][] arr, int r, int c)
|
|
|
{
|
|
|
if (arr[r][c] == 'P')
|
|
|
{
|
|
|
arr[r][c] = 'W';
|
|
|
display(arr);
|
|
|
fillGrid(arr, r + 1, c);
|
|
|
fillGrid(arr, r - 1, c);
|
|
|
fillGrid(arr, r, c + 1);
|
|
|
fillGrid(arr, r, c - 1);
|
|
|
}
|
|
|
}
|
|
|
/** Function to display grid **/
|
|
|
private void display(char[][] arr)
|
|
|
{
|
|
|
System.out.println("\nGrid : ");
|
|
|
for (int i = 1; i < arr.length - 1; i++)
|
|
|
{
|
|
|
for (int j = 1; j < arr[i].length - 1; j++)
|
|
|
System.out.print(arr[i][j] +" ");
|
|
|
System.out.println();
|
|
|
}
|
|
|
}
|
|
|
|
|
|
/** Main method **/
|
|
|
public static void main(String[] args)
|
|
|
{
|
|
|
Scanner scan = new Scanner( System.in );
|
|
|
System.out.println("Flood Fill Test\n");
|
|
|
/** Accept dimensions **/
|
|
|
System.out.println("Enter dimensions of grid");
|
|
|
int M = scan.nextInt();
|
|
|
int N = scan.nextInt();
|
|
|
/** make grid with border as obstacle to avoid boundary conditions **/
|
|
|
char[][] arr = new char[M + 2][N + 2];
|
|
|
for (int i = 0; i < M + 2; i++)
|
|
|
Arrays.fill(arr[i], 'O');
|
|
|
/** Accept grid **/
|
|
|
System.out.println("Enter grid with 'P' for passage and 'O' for obstacle");
|
|
|
for (int i = 1; i < M + 1; i++)
|
|
|
for (int j = 1; j < N + 1; j++)
|
|
|
arr[i][j] = scan.next().charAt(0);
|
|
|
System.out.println("Enter coordinates to start ");
|
|
|
int sr = scan.nextInt();
|
|
|
int sc = scan.nextInt();
|
|
|
if (arr[sr][sc] != 'P')
|
|
|
{
|
|
|
System.out.println("Invalid coordinates");
|
|
|
System.exit(0);
|
|
|
}
|
|
|
FloodFill ff = new FloodFill();
|
|
|
ff.fillGrid(arr, sr, sc);
|
|
|
}
|
|
|
}
|
|
|
|
|
|
/*
|
|
|
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 |