Counting Connected Regions in a Labyrinth

You are given a labyrinth represented as an n×m grid consisting of passable cells (denoted by '.') and impassable cells (denoted by '#'). Your task is to count the number of distinct connected regions formed by passable cells. Two cells are considered connected if they are adjacent horizontally or vertically.

The solution requires an understanding of depth-first search (DFS) or breadth-first search (BFS) for traversing grids. The answer should read the labyrinth from standard input and output the number of connected regions to standard output.

The connectivity is defined as follows:

Two cells \( (i,j) \) and \( (k,l) \) are in the same region if there exists a sequence of cells starting with \( (i,j) \) and ending with \( (k,l) \) such that each consecutive pair of cells in the sequence are adjacent (up, down, left, or right) and are passable.

inputFormat

The first line contains two integers, n and m, representing the number of rows and columns of the labyrinth respectively.

The following n lines each contain a string of length m that represents a row in the labyrinth. Each character is either a '.' (passable cell) or a '#' (impassable cell).

The input is provided via standard input.

outputFormat

Output a single integer representing the number of distinct connected regions of passable cells in the labyrinth.

The output should be written to standard output.

## sample

4 5
.#.#.
###..
..#..
..###

4