Coast Length

Interview

Time limit1sMemory limit256 MB

Summary

Count the total length of borders between land and sea connected to the outside of the grid, excluding enclosed lakes.

Level: Medium4 of 10
Topics: BFS, Graph, Matrix
Solved: No attempts yet

Problem

Soteholm is an island municipality that has to write an action plan for its greenhouse gas emissions. The residents read the IPCC report on climate change and decided that rising sea level is the effect that reaches their municipality hardest. They value their coast, so before they take a position they want to know whether the total length of that coast grows or shrinks. Height maps already told them which squares go under water, and what is left is measuring the coast.

The map of Soteholm is an $N \times M$ grid. Each square has side length 1 km and is either water or land. Two squares are connected when they share an edge. Everything outside the map is sea. Sea is any water that reaches the outside of the map through water only. The coast is every border between land and sea, and you have to report its total length. The shore of a lake enclosed by land, and any island inside such a lake, is not part of the coast.

In the figure, gray squares are land and white squares are water, and the thick black line is the coast. The figure corresponds to the first example input.

Input

The first line contains two integers $N$ and $M$ separated by a space ( $1 \le N, M \le 1000$ ).

Each of the next $N$ lines contains a string of length $M$ made of zeros and ones. A zero is water and a one is land.

Output

Print the total length of the coast in km as one integer on a single line.

Examples6

Example 1

Input

Expected output

Example 2
Input
```
1 1
0
```
Expected output
```
0
```
Example 3
Input
```
1 1
1
```
Expected output
```
4
```
Example 4
Input
```
3 3
111
111
111
```
Expected output
```
12
```
Example 5
Input
```
3 3
101
010
101
```
Expected output
```
20
```
Example 6
Input
```
4 5
00000
00000
00000
00000
```
Expected output
```
0
```