NKGUARD.cpp

#include<iostream>
using namespace std;

const int MAX = 705;

int N,M;                // Lần lượt là số lượng hàng, cột của ma trận
int Answer;             // Kết quả là số lượng đỉnh đồi
int Map[MAX][MAX];      // Bản đồ của nông trang

bool Visit[MAX][MAX];   // Đánh dấu để kiểm tra đã duyệt hay chưa
bool IsHill;            // Đánh dấu xem có phải là đỉnh đồi hay không

int drow[8] = {-1,-1,-1, 0,0, 1,1,1};
int dcol[8] = {-1, 0, 1,-1,1,-1,0,1};

void DFS(int row, int col)
{
	// Tại mỗi điểm ta sẽ đánh dấu điểm đó đã được duyệt
	Visit[row][col] = true;

	for(int i = 0; i < 8; i++)
	{
		int r = row + drow[i];
		int c = col + dcol[i];

		if(r >= 0 && r < N && c >= 0 && c < M)
		{
			// Tại một điểm mà tồn tại 1 điểm kề có giá trị lớn hơn
			// thì điểm đó không phải đỉnh đồi
			if(IsHill && Map[r][c] > Map[row][col]) IsHill = false;

			// Duyệt tới các điểm có cùng độ cao mà chưa được duyệt
			// vì các điểm đó sẽ thuộc cùng 1 đỉnh đồi.
			if(Map[r][c] == Map[row][col] && !Visit[r][c]) DFS(r, c);
		}
	}
}

int main()
{
	//freopen("input.txt","r",stdin);
	ios::sync_with_stdio(false);

	// Nhập đầu vào
	cin >> N >> M;
	for(int i = 0; i < N; i++)
		for(int j = 0; j < M; j++)
		{
			cin >> Map[i][j];
			Visit[i][j] = false;
		}

	// Duyệt từng phần tử trong ma trận
	// và kiểm tra tại phần tử chưa được xét
	for(int i = 0; i < N; i++)
		for(int j = 0; j < M; j++)
			if(!Visit[i][j])
			{
				// Khởi tạo IsHill = true, sau đó sử dụng thuật toán DFS
				// để duyệt ma trận. Sau quá trình duyệt, nếu như IsHill vẫn có 
				// giá trị true thì chứng tỏ điểm vừa xét là đỉnh đồi.
				IsHill = true;
				DFS(i, j);
				if(IsHill) Answer++;
			}

	// In kết quả số đỉnh đồi
	cout << Answer << endl;

	return 0;
}