Description

On an isolated island, there is an interesting phenomenon: households from the same family are always adjacent (adjacent means the four cardinal directions), while different families are always separated by rivers or hills. However, people from the same family do not necessarily share the same surname. Given the island’s map, find how many different families there are on the island. The map has $n$ rows, each with several columns. Each cell is either a space, meaning sea; or $\text{``{\tt *}''}$, meaning a river or hill; or a lowercase letter, meaning a household’s surname.

Input Format

The first line contains a number $N$, indicating the number of lines that follow. Then come $N$ lines of characters, each consisting of lowercase letters and the character $\texttt *$. Some lines may also begin with several consecutive spaces, meaning those areas are sea. Each line has at most $200$ characters.

Output Format

A single number, indicating the number of families.

4
*zlw**pxh
l*zlwk*hx*
w*tyy**yyy
        zzl

3

Hint

Constraints

• For $10\%$ of the testdata, $n \le 1$.
• For $30\%$ of the testdata, $n \le 10$.
• For $100\%$ of the testdata, $n \le 100$, and each line has at most $200$ characters.

NOI Guide 2010 Junior (10).

Translated by ChatGPT 5