On February 30th this year
astronauts from the International Space Station flew over the Pacific Ocean and
took a picture, on which was discovered a previously unknown island. On the
digitized picture the island appears as a connected set of square cells. This
means that someone can reach some cell of land from some other cell land, going
from cell to cell through their common side. There is no other water area
within the island. The island is surrounded by water.
The coastline of the island is a closed
polygonal line. The water cell are marked by minus sign ("–"), and
the land cell – by plus sign ("+").
The coastline cell is a cell, which have a
common border with water cell. In the figure below the length of the coastline
is 14 cells. The other five cells of land are internal cells of the island.
Write a program that, given dimensions of the
rectangle n and m and digitized picture, calculates
l – the number of cells that form the coastline of the island.
Limitations
3 <= n, m
<= 1 000, l > 0.
Input
The first line of input file contains two integers n and m. The following n
lines contain m characters (the char "–" – cell with
water, and the "+" – cell with land)
Output (Output)
The output file should consist of one integer l
– the number of cells that form the coastline of the island.
Examples
Input
|
Output
|
|
7 8
––––––––
–––+++––
–––+++––
–+++++––
–+++++––
––++–+––
––––––––
|
14
|
Input
|
Output
|
|
3 3
–––
–+–
–––
|
1
|
All Rybinsk-2012 problems (in PDF)
