baovenongtrang

 avatar
duyvan
plain_text
2 years ago
1.5 kB
11
Indexable
#include<iostream>
#define endl '\n'
using namespace std;

struct Node{
	int r,c;
};
int M,N;
int map[1001][1001];
int visit[1001][1001];
int dx[] = {0,0,1,-1,1,-1,1,-1};
int dy[] = {1,-1,0,0,1,-1,-1,1};
int front, rear;
int ans;
Node queue[500000];

void en(int i, int j)
{
	rear++;
	queue[rear].r = i;
	queue[rear].c = j;
}

Node de()
{
	front++;
	return queue[front];
}
void input()
{
	cin >> N >> M;
	for(int i = 0; i < N; ++i)
		for(int j = 0; j < M; ++j)
			cin >> map[i][j];
}

int check(int x, int y)
{
	int answer = 1;
	int value = map[x][y];
	front = rear = -1;
	en(x,y);
	visit[x][y] = 1;
	while(front != rear)
	{
		Node tmp = de();
		for(int i = 0; i < 8; ++i)
		{
			int Nx = tmp.r + dx[i];
			int Ny = tmp.c + dy[i];
			if(Nx >= 0 && Nx < N && Ny >= 0 && Ny < M)
			{
				if(map[Nx][Ny] == value && visit[Nx][Ny] == 0)
				{
					en(Nx, Ny);
					visit[Nx][Ny] = 1;
				}
				if(map[Nx][Ny] > map[tmp.r][tmp.c])	answer = 0;
			}
		}
	}
	return answer;
}

void reset()
{
	for(int i = 0; i < N; ++i)
		for(int j = 0; j < M; ++j)
			visit[i][j] = 0;
}

int main()
{
/*	ios::sync_with_stdio(false);
	freopen("INP.txt","r",stdin);
	freopen("OUT.txt","w",stdout);
	cin.tie(0);*/

	int T;
	cin >> T;
	for(int tc = 1; tc <= T; ++tc)
	{
		ans = 0;
		input();
		for(int i = 0; i < N; ++i)
			for(int j = 0; j < M; ++j)
				if(visit[i][j] == 0 && check(i,j) == 1)
					ans++;
		cout << "#" << tc << " "  << ans << endl;
		reset();
	}
	return 0;
}
Editor is loading...