P1454 Aurora on Christmas Night

Christmas Night series.

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. ^_^

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 one integer $s$ on a single line.

Constraints: $1 \le n, m \le 100$. Hint: DFS. Translated by ChatGPT 5