Count the Number of Islands

Given a grid of size $N \times M$, where each cell is either land (L) or water (W), your task is to count the number of islands. An island is defined as a maximal set of connected land cells. Two cells are considered connected if they are adjacent horizontally or vertically (i.e. in one of the four cardinal directions: up, down, left, right, formally represented by $\{(-1,0), (1,0), (0,-1), (0,1)\}$).

You are required to implement a depth-first search (DFS) to explore and mark visited land cells. Once all connected cells of an island are visited, you count it as one island. The exploration continues until all cells in the grid are processed.

inputFormat

The input is read from standard input (stdin). The first line contains two integers $N$ and $M$ — the number of rows and columns of the grid. This is followed by $N$ lines, each containing a string of $M$ characters. Each character is either L (representing land) or W (representing water).

outputFormat

Output a single integer to standard output (stdout) representing the number of islands in the grid.

4 5
LWLWL
LLWWL
WLWWL
WWWLL

3