10761076 SUSTech Online Judge
Problem 1076 --Connected Regions

## 1076: Connected Regions

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 525  Solved: 187
[Submit][Status][Web Board]

## Description

There are C kinds of colors and n * m grids. Each grid was paint by one color. Grid u at position (x, y) and grid v at position (a,b) are connected if and only if (1) they have the same color, (2) (|x-a| = 0 and |y-b|=0) or (|x-a| = 1 and |y-b|=0) or (|x-a|=0 and |y-b|=1). In a n * m grids, it contains several connected grids. Now give you n, m, C and the color of each grid. Please print the number of connected regions in it.

## Input

The first line will be an integer T. (1 <= T <= 50) T is the number of test case.

For each test case, the first line will be three integers n, m, C. (1 <= n, m, C <= 1000). All colors are labeled from 1 to C.

Then there will be n x m integers. The number in ith line and jth column means the color of the grid.

## Output

For each test case, print the number of connected block.

## Sample Input

2
3 3 2
2 2 2
2 1 2
2 2 2
5 5 5
1 2 3 4 5
1 2 3 4 5
1 3 2 4 5
1 5 4 2 3
1 5 4 2 3


## Sample Output

2
11


## HINT

For the first sample, the 2 outside is one
connect block, the 1 inside is the other.

For the second sample, {1,1,1,1,1},
{2,2},{3,3},{4,4,4},{5,5,5},{3},{2},{5,5},{4,4},{2,2},{3,3} are all connected
blocks. Totally 11.

[Submit][Status]