P1767 Family

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.

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.

A single number, indicating the number of families.

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