Counting Regions in a Maze

Given a maze represented as a grid with # denoting walls and . denoting open cells, your task is to determine the number of distinct regions of connected open cells. Two cells are connected if they are adjacent horizontally or vertically.

Mathematically, if we denote the maze as a grid of size \( n \times m \) and define \( A[i][j] \) as the cell at row \( i \) and column \( j \), then we say two open cells \( A[i][j] \) and \( A[k][l] \) belong to the same region if there exists a sequence \( (i_1,j_1), (i_2,j_2), \ldots, (i_t,j_t) \) such that \( (i_1,j_1) = (i,j) \), \( (i_t,j_t) = (k,l) \), and for every \( 1 \leq p < t \), \( |i_p-i_{p+1}| + |j_p-j_{p+1}| = 1 \).

Your program should efficiently count such regions, even in cases where the maze is large.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains two integers \( n \) and \( m \), representing the number of rows and columns in the maze, respectively.
• The following \( n \) lines each contain a string of length \( m \) consisting of characters # (wall) and . (open cell).

outputFormat

Output a single integer to standard output (stdout) which is the number of distinct regions of connected open cells.

## sample

3 3
###
#.#
###

1

</p>