Counting Contiguous Regions in a Grid

Given a grid of cells, where each cell is either open (denoted by '.') or blocked (denoted by '#'), your task is to compute the number of discrete contiguous regions consisting solely of open cells. Two open cells are considered part of the same region if they are adjacent horizontally or vertically (diagonals are not considered adjacent).

Please note that the grid is provided with its dimensions in the first line, followed by rows of the grid. Your solution should read from standard input and write the result to standard output.

Constraints:

• 1 ≤ N, M ≤ 1000 (where N is the number of rows and M is the number of columns)

Use efficient algorithms to ensure your program runs within acceptable time limits.

inputFormat

The first line of input contains two integers N and M separated by a space, representing the number of rows and columns of the grid respectively. The following N lines each contain a string of length M consisting of characters '.' (open cell) or '#' (blocked cell).

outputFormat

Output a single integer representing the number of contiguous regions consisting of open cells found in the grid.

5 6
.##..#
#...##
.##..#
###..#
#..##.

5