Connected Components in a Grid

You are given a grid composed of two types of cells: . (empty) and * (blocked). Your task is to determine the number of connected components of empty cells. Two empty cells are connected if they share a side (up, down, left, or right).

The grid is provided in row-major order. Compute and output an integer representing the number of distinct connected regions of empty cells.

Hint: Use depth-first search (DFS) or breadth-first search (BFS) to traverse the grid.

inputFormat

The first line of input contains two integers, n and m, denoting the number of rows and columns in the grid. This is followed by n lines, each containing a string of m characters representing a row of the grid.

Example input:

5 5
..*..
..*..
*****
..**.
..*..

outputFormat

Output a single integer which is the number of connected components of empty cells in the grid.

5 5
..*..
..*..
*****
..**.
..*..

4