ICPC PACNW 2016 G - Maximum Islands

View as PDF

Submit solution


Points: 15
Time limit: 1.0s
Memory limit: 256M

Problem type

You are mapping a faraway planet using a satellite.

Your satellite has captured an image of the planet's surface. The photographed section can be modeled as a grid. Each grid cell is either land, water, or covered by clouds. Clouds mean that the surface could either be land or water, but we can't tell.

An island is a set of connected land cells. Two cells are considered connected if they share an edge.

Given the image, determine the maximum number of islands that is consistent with the given information.

Input

The first line of input contains two space-separated integers n and m (1 \le n, m \le 40).

Each of the next n lines contains m characters, describing the satellite image. Land cells are denoted by L, water cells are denoted by W, and cells covered by clouds are denoted by C.

Output

Print, on a single line, a single integer indicating the maximum number of islands that is consistent with the given grid.

Sample Input

5 4
LLWL
CCCC
CCCC
CCCC
LWLL

Sample Output

8
Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported

Comments

There are no comments at the moment.