Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
1.9 kB
2
Indexable
// In Practice, You should use the statndard input/output
// in order to receive a score properly.
// Do not use file input and output. Please be very careful. 

#include<iostream>

using namespace std;
#define size 100000
int N,M;
int map[705][705];
int queue[size];
int front=-1;
int dem;
int rear =-1;
int dx[8]={-1,-1,-1,0,1,1,1,0};
int dy[8]={-1,0,1,1,1,0,-1,-1};
int visit[705][705];
void nhap()
{
	for(int i=0;i<N;i++){
		for(int j=0; j<M;j++){
			cin>>map[i][j];
		}

	}

}
void reset(){                               // reset mang de bfs
	for(int i=0; i<705;i++){
		for(int j=0; j<705;j++){
			visit[i][j]=0;
		}

	}

}


bool isEmpty(){
	return front==rear;
}
void push(int x){
	if(rear == size-1) rear=-1;
	rear++;
	queue[rear]=x;
}
int pop(){
	if(front==size-1) front=-1;
	front++;
	 return queue[front];
}

void bfs(int x, int y){
	
	visit[x][y] = 1;
	push(x);
	push(y);
	int tmp = 1;
	while(!isEmpty()){
		int hang = pop();
		int cot = pop();
		for(int i = 0; i < 8; i++){
			int h = hang + dx[i];
			int c = cot + dy[i];
			if(h >= 0 && h < N && c >= 0 && c < M){
				if(visit[h][c] == 0 && map[h][c] == map[hang][cot]){
					visit[h][c] = 1;
					push(h);
					push(c);
				} else {
					if(map[h][c] > map[hang][cot]){
						tmp = 0;
					}
				}
			}
		}
	}
	dem = dem + tmp;
}




int main(int argc, char** argv)
{
	int test_case;
	int T;
	//freopen("text.txt", "r", stdin);
	cin >> T;

	/*
	   Read each test case from standard input.
	*/
	for(test_case = 1; test_case <= T; ++test_case)
	{
		cin>>N>>M;
		reset();
		nhap();
		dem = 0;
		for(int i = 0; i < N; i++){
			for(int j = 0; j < M; j++){
				if(visit[i][j] == 0){
					bfs(i, j);
				}
			}
		}
		
		cout << "#" << test_case << " " << dem << endl;
	}
	return 0;//Your program should return 0 on normal termination.
}