#C4347. Merged Container Count

    ID: 47875 Type: Default 1000ms 256MiB

Merged Container Count

Merged Container Count

You are given a grid of characters, where each cell represents a container of a type denoted by a lowercase or uppercase letter. Containers that are connected horizontally or vertically and share the same character are considered merged into a single group. Your task is to count the number of such merged container groups for each test case.

The input consists of multiple test cases. Each test case begins with two integers n and m indicating the number of rows and columns in the grid, respectively, followed by n lines of exactly m characters. The input terminates with a test case where n = 0 and m = 0, which should not be processed.

Note: Connections are considered only in the four cardinal directions (up, down, left, right).

inputFormat

The input is read from standard input (stdin). It contains multiple test cases. For each test case:

  • The first line contains two integers n and m -- the number of rows and columns in the grid.
  • The next n lines each contain a string of length m representing a row of the grid.

The last test case is indicated by a line containing "0 0" which should not be processed.

outputFormat

For each test case, output a single integer on a separate line representing the number of merged container groups in that grid. The output is written to standard output (stdout).

## sample
3 4
aaaa
aaaa
bbbb
2 3
ccc
ccc
0 0
2

1

</p>