IN JAVA

WITH FLOODFILL ALOGRITHM

Simple code

Task

The tasks is to write a recursive program to count the number of muck-free regions. The IRL is represented by a two-dimensional rectangle squares. Each square contains either muck ('M') or sand ('.'). A region is defined as a connected set of one of more squares with sand in it, where a square is considered to connect to all eight of its adjacent squares.

Floodfill algorithm

The task can be accomplished quite easily with a well-know, recursive algorithm called floodfill. This algorithm 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. It is a particularly easy algorithm to implement recursively on a two dimensional grid.

The algorithm works by "painting" or "flooding" the current cell and then recursing on all the neightboring cells. It is necessary to avoid going into regions that are already flooded or inaccessible.

Input Format

All the input comes from the standard input stream. The first line of the input consists of two space-separated integers: N and M (1 <= N <= 100; 1 <= M <= 100). The remaining N lines consist of M characters each. Each character is either 'M' or '.' representing one square in the IRL. The characters do not have spaces between them.

SAMPLE INPUT

10 12 .MMMMMMMM..M M...MMMMM... MMMM..MMM..M MMMMMMMMM..M MMMMMMMMM.MM MM.MMMMMM.MM M.M.MMMMM..M .M.M.MMMMM.M M.M.MMMMMM.M MM.MMMMMMM.M 

SAMPLE OUTPUT

The number of muck free spots in the input:

3

One spot is in the upper left, one down the right side, and the third one is spread out n the lower left corner.