Baovenongtrang

Level 4
Bao ve nong trang
Nông trang có rất nhiều ngọn đồi núi, để bảo vệ nông trang nông dân John muốn đặt người canh gác trên các ngọn đồi này.

Anh ta băn khoăn không biết sẽ cần bao nhiêu người canh gác nếu như anh ta muốn đặt 1 người canh gác trên đỉnh của mỗi đồi. Anh ta có bản đồ của nông trang là một ma trận gồm N (1 < N <= 700) hàng và M (1 < M <= 700) cột. Mỗi phần tử của ma trận là độ cao H_ij so với mặt nước biển (0 <= H_ij <= 10,000) của ô (i, j). Hãy giúp anh ta xác định số lượng đỉnh đồi trên bản đồ.

Đỉnh đồi là 1 hoặc nhiều ô nằm kề nhau của ma trận có cùng độ cao được bao quanh bởi cạnh của bản đồ hoặc bởi các ô có độ cao nhỏ hơn. Hai ô gọi là kề nhau nếu độ chênh lệch giữa tọa độ X không quá 1 và chênh lệch tọa độ Y không quá 1.

[Input]

* Dòng 1: Số lượng mẫu

* Dòng 2: Hai số nguyên cách nhau bởi dấu cách: N và M

* Dòng 3: N+1: Dòng i+1 mô tả hàng i của ma trận với M số nguyên cách nhau bởi dấu cách: H_ij

[Output]

* Dòng 1: Một số nguyên duy nhất là số lượng đỉnh đồi.

[Sample]

[Input]

3
8 7
4 3 2 2 1 0 1
3 3 3 2 1 0 1
2 2 2 2 1 0 0
2 1 1 1 1 0 0
1 1 0 0 0 1 0
0 0 0 1 1 1 0
0 1 2 2 1 1 0
0 1 1 1 2 1 0
8 7
4 3 2 2 1 1 1
3 3 3 2 1 0 1
2 2 2 2 1 0 0
2 1 1 1 1 0 0
1 1 0 0 0 1 0
0 0 0 1 1 1 0
0 1 2 2 1 1 0
0 1 1 1 2 1 0
8 7
4 3 2 2 1 1 1
3 3 3 2 1 0 1
2 2 2 2 1 0 0
2 1 1 2 1 0 0
1 1 2 2 0 1 0
0 0 0 2 1 1 0
0 1 2 2 1 1 0
0 1 1 1 2 1 0

 

[Output]

#1 3
#2 2
#3 1


#1 36766
#2 247
#3 6917
#4 35742
#5 17063
#6 10417
#7 17220
#8 547
#9 4409
#10 1727
#11 8660
#12 6250
#13 440
#14 24755
#15 5359
#16 4634
#17 36911
#18 6365
#19 18747
#20 11721
#21 6442
#22 29309
#23 2177
#24 8409
#25 5612
#26 8113
#27 9211
#28 13113
#29 6848
#30 38756
#31 6717
#32 1101
#33 1837
#34 4403
#35 431
#36 1026
#37 25110
#38 6890
#39 23979
#40 3339
#41 7192
#42 8714
#43 14115
#44 1945
#45 1626
#46 9917
#47 18989
#48 3647
#49 3024
#50 4436
#include <iostream>
using namespace std;

int T, n, m, result, cnt;
int mp[701][701], vs[701][701];
bool isTop;

void resetVs(){
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++) vs[i][j] = 0;
	}
}

int q[500001][2];
int head, tail;

int dx[8] = {-1, 1, 0, 0, 1, 1, -1, -1};
int dy[8] = {0, 0, -1, 1, -1, 1, -1, 1};

void init(){
	cnt = 0;
	head = 0, tail = 0;
	result = 0;
	resetVs();
}

void push(int x, int y){
	q[tail][0] = x, q[tail++][1] = y;
}

void pop(){
	head++;
}

bool isEmpty(){
	return head == tail;
}

int getX(){
	return q[head][0];
}

int getY(){
	return q[head][1];
}

void bfs(int X, int Y){
	push(X, Y);
	vs[X][Y] = 1;
	isTop = true;

	while(!isEmpty()){
		int x = getX();
		int y = getY();
		
		pop();
		for(int i = 0; i < 8; i++){
			int xx = x + dx[i];
			int yy = y + dy[i];
			if(xx >= 1 && xx <= n && yy >= 1 && yy <= m){
				if(mp[xx][yy] == mp[x][y] && !vs[xx][yy]){
					vs[xx][yy] = 1;
					push(xx, yy);
				} else if(mp[xx][yy] > mp[x][y]){
					isTop = false;
				}
			}
		}
	}
}

int main(){
	freopen("input.txt", "r", stdin);
	cin >> T;

	for(int tc = 1; tc <= T; tc++){
		// Input
		cin >> n >> m;
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= m; j++) cin >> mp[i][j];
		}

		// Initial
		init();

		// Solve Problem
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= m; j++){
				if(!vs[i][j]){
					bfs(i, j);
					if(isTop) result++;
				}
			}
		}

		// Output
		cout << "#" << tc << " " << result << endl;
	}

	return 0;
 }