Counting Sections in a Grid

You are given an N by M grid where each cell is either an empty cell denoted by . or a divider denoted by #. Two empty cells are considered connected if they share a common side (up, down, left, or right). Your task is to determine the number of distinct sections (i.e., connected components) of empty cells in the grid.

Mathematically, if we define the grid as a graph where each empty cell is a node and there is an edge between two nodes if the corresponding cells are adjacent horizontally or vertically, you need to compute the number of connected subgraphs of empty cells. For example, the number of connected components can be described as:

$$\text{components} = \text{number of connected subgraphs in } G$$

This problem is a typical application of depth-first search (DFS) or breadth-first search (BFS) on grids.

inputFormat

The input is given via standard input (stdin) with the following format:

1. The first line contains two integers N and M $(1 \leq N, M \leq 1000)$, representing the number of rows and columns respectively.
2. The next N lines each contain a string of M characters composed of . and #, representing the grid.

outputFormat

Output a single integer (to stdout): the number of distinct sections (connected components) of empty cells in the grid.

1 1
.

1