Counting Independent Crop Regions in a Farmland Grid

Given a farmland divided into a grid of N × M blocks, each block contains either a crop represented by the capital letter R or a weed represented by the capital letter X. A crop region is defined as a set of connected blocks (adjacent in the four cardinal directions: up, down, left, right) containing R. An independent crop region is one that is entirely surrounded by weeds. Formally, for any block in an independent crop region, each of its four neighboring positions that is not part of the region is occupied by a weed. Note that cells outside the grid are also considered to be weeds, i.e. the area beyond the N × M grid.

Your task is to compute the number of independent crop regions in the given grid. For example, if the grid is a 4 × 4 farmland as follows:

RXXX
XRRX
XRRX
XXXR

There are 3 independent crop regions.

The problem can be mathematically described using the following notation:

Let the farmland be represented as a 2D grid G of size $$N \times M$$. Two cells (i, j) and (k, l) are connected if \(|i-k|+|j-l|=1\). A region C (a connected set of cells with value R) is an independent crop region if for any cell (i, j) \in C and any neighboring cell (u, v) not in C, either (u, v) is outside the grid (and considered as weed) or G[u][v] is X.

inputFormat

The first line of the input contains two integers, N and M.

Then follow N lines, each containing a string of length M, representing the grid. The characters in the string are either R (crop) or X (weed).

All indices are 0-indexed.

outputFormat

Output a single integer, the number of independent crop regions in the grid.

sample

1 1
R

1