Description

Santa Claus has returned to the Arctic Christmas Zone; it is almost 12 o'clock, which means the aurora show is about to begin. Here the aurora is not the natural polar lights but a man-made display directed by Santa.

Boom... fireworks go off (from Liuyang, the hometown of fireworks in China). Then comes the aurora show.

The man-made aurora is actually a series of $n \times m$ dot-matrix images in the sky. Each point has only two states: lit or unlit. The lit points together form beautiful pictures. Each picture consists of several (exactly $s$) “patterns”. Santa defines a “pattern” strictly as follows: view lit points as vertices of a graph where two lit points are adjacent if their Manhattan distance is at most $2$. For $A(x_1, y_1)$ and $B(x_2, y_2)$, the Manhattan distance between $A$ and $B$ is $|x_1 - x_2| + |y_1 - y_2|$. A “pattern” is a connected component of this graph. The elves watch the aurora and count the number of patterns in each image, singing and dancing through a beautiful Christmas night. ^_^

Input Format

The first line contains two integers $n$ and $m$.

The next $n$ lines each contain $m$ characters. In the $i$-th line, the $j$-th character is - if the point is unlit, or # if the point is lit. No other characters appear.

Output Format

Output one integer $s$ on a single line.

19 48
------------------------------------------------
---####-----#-----#----------------------####---
--######----#-----#---------------------######--
-########--#-#---#-#####--#-##-##---#--########-
-###--###--#-#---#-#----#-##-##--#--#--###--###-
-###--###--#--#-#--######-#--#---#-#---###--###-
-########--#--#-#--#------#--#----##---########-
--######---#---#---######-#--#-----#----######--
---####----------------------------#-----####---
----------------------------------#-------------
------------------------------------------------
---###--#--------#------#-----------------------
--#---#-#---------------#-----------------------
-#------#-##--#-##--##-###-#-##-###--###-#--##--
-#------##--#-##-#-#----#--##--#---##---##-#----
-#------#---#-#--#--#---#--#---#---##----#--#---
--#---#-#---#-#--#---#--#--#---#---##---##---#--
---###--#---#-#--#-##---#--#---#---#-###-#-##---
------------------------------------------------

4

Hint

Constraints: $1 \le n, m \le 100$.

Hint: DFS.

Translated by ChatGPT 5