baovenongtrang
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...