Minimum number of islands

Interview

Time limit2sMemory limit512 MB

Summary

Given a grid of land, water, and cloud cells, find the minimum possible number of 4-connected land islands if every cloud can be either land or water.

Level: Medium5 of 10
Topics: Graph, DFS, Greedy, Union-find
Solved: No attempts yet

Problem

You are mapping a faraway planet with a satellite. The planet's surface is a grid, and the satellite captured one image of that surface. Each grid cell is land (written as 'L'), water (written as 'W'), or covered by clouds (written as 'C'). A cell covered by clouds can be either land or water, and you cannot tell which.

An island is a region of land cells in which every two cells are connected to each other by a path that only moves up, down, left, or right.

Given the image, find the smallest number of islands that is consistent with it.

Input

The first line contains the number of rows $r$ and the number of columns $c$ of the image ( $1 \le r, c \le 50$ ).

Each of the next $r$ lines contains exactly $c$ characters. Every character is 'L' for land, 'W' for water, or 'C' for clouds.

Output

Print a single integer, the smallest possible number of islands.

Examples4

Example 1
Input
```
4 5
CCCCC
CCCCC
CCCCC
CCCCC
```
Expected output
```
0
```
Example 2
Input
```
3 2
LW
CC
WL
```
Expected output
```
1
```
Example 3
Input
```
1 1
L
```
Expected output
```
1
```
Example 4
Input
```
3 3
LWL
WWW
LWL
```
Expected output
```
4
```