Beach

Interview

Time limit2sMemory limit512 MB

Summary

Count the hexagon edges that separate land from water, ignoring any edge on the outer border of the map.

Level: Medium4 of 10
Topics: Implementation, Matrix, Simulation, Geometry
Solved: No attempts yet

Problem

You are given a map made of unit regular hexagons. Write a program that computes the length of the beach.

A beach is a hexagon edge with water on one side and land on the other. Each edge has length 1. The area outside the map counts as neither water nor land, so an edge on the border of the map is never a beach.

The map has $N$ rows, and each row is $M$ hexagons placed side by side. Counting from the top, every even-numbered row (the 2nd, the 4th, and so on) is shifted half a cell to the right of the row directly above it. The figure below shows the map of the second example, with the beach edges drawn in red.

Input

The first line contains the height $N$ and the width $M$ of the map. ( $1 \le N, M \le 50$ )

Each of the next $N$ lines contains one row of the map as a string of length $M$ . . is water and # is land.

Output

Print the length of the beach on the first line.

Examples4

Example 1
Input
```
1 8
.#...#..
```
Expected output
```
4
```
Example 2
Input
```
3 6
..#.##
.##.#.
#.#...
```
Expected output
```
19
```
Example 3
Input
```
2 10
#...#.....
##..#...#.
```
Expected output
```
15
```
Example 4
Input
```
4 6
....#.
.#....
..#..#
####..
```
Expected output
```
24
```