Untitled

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.

package Lesson_10;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Bao_ve_Nong_Trai {
	static int T, N, M, cr, cc, nr, nc, count;
	static int map[][];
	static boolean visited[][];
	static int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
	static int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};
	
	public static class Queue{
		static int front, rear, Data[];
		
		public Queue() {
			front = rear = -1;
			Data = new int[500000];
		}
		
		public static void reset(){
			front = rear = -1;
		}
		
		public static void enQueue(int value){
			Data[++rear] = value;
		}
		
		public static int deQueue(){
			return Data[++front];
		}
		
		public static boolean is_Empty(){
			if(front == rear) return true;
			return false;
		}
	}
	
	public static void main(String[] args) throws FileNotFoundException{
		System.setIn(new FileInputStream("Bao_ve_NongTrai"));
		Scanner scanner = new Scanner(System.in);
		T = scanner.nextInt();
		for(int tc = 1; tc <= T; tc++){
			N = scanner.nextInt();
			M = scanner.nextInt();
			map = new int[N][M];
			visited = new boolean[N][M];
			for(int i = 0; i < N; i++){
				for(int j = 0; j < M; j++){
					map[i][j] = scanner.nextInt();
				}
			}
			Queue rQueue = new Queue();
			Queue cQueue = new Queue();
			count = 0;
			int check;
			for(int i = 0; i < N; i++){
				for(int j = 0; j < M; j++){
					check = 0;
					if(map[i][j] != 0 && visited[i][j] == false){
						rQueue.reset();
						cQueue.reset();
						rQueue.enQueue(i);
						cQueue.enQueue(j);
						visited[i][j] = true;
						while(!rQueue.is_Empty()){
							cr = rQueue.deQueue();
							cc = cQueue.deQueue();
							for(int k = 0; k < 8; k++){
								nr = cr + dx[k];
								nc = cc + dy[k];
								if(0 <= nr && nr < N && 0 <= nc && nc < M){
									if( map[nr][nc] == map[cr][cc] && !visited[nr][nc]){
										visited[nr][nc] = true;
										rQueue.enQueue(nr);
										cQueue.enQueue(nc);
									}
									if(map[nr][nc] > map[cr][cc]){
										check = 1;
									}
								}
							}
						}
						if(check == 0){
							count++;
						}
					}
					
					
					
				}
			}
			System.out.println("#"+tc + " " + count);
		}
	}
}

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