SPOJ.COM - Thuật toán bài NKGAURD - Bảo vệ nông trang

Đề bài:

Nông trang có rất nhiều ngọn đồi núi, để bảo vệ nông trang nông dân Thái 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.

Đầu vào

• Dòng 1: Hai số nguyên cách nhau bởi dấu cách: N và M

• Dòng 2..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

Đầu ra

• Dòng 1: Một số nguyên duy nhất là số lượng đỉnh đồi.

Ví dụ

Đầu vào:

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 

Đầu ra:

3 

Bạn có thể tham khảo link gốc đề bài và submit code tại đây: http://vn.spoj.com/problems/NKGUARD/

Phân tích

Theo đầu bài, đỉ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. Do đó, mình sẽ sử dụng thuật toán tìm kiếm theo chiều sâu DFS hoặc thuật toán tìm kiếm theo chiều rộng BFS. Cả 2 cách đều tương tự nhau (ở đây mình chỉ trình bày code theo thuật toán tìm kiếm theo chiều sâu DFS).

Tiếp theo, 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. Nghĩa là một ô sẽ có 8 ô xung quanh kề với nó.

Lời giải

Bạn nên tự mình nghĩ ra thuật toán của bài toán trước khi tham khảo code của mình nhé. Hãy phát huy tối đa khả năng sáng tạo của bản thân. Hơn nữa code mình viết ra cũng chưa thật sự tối ưu. Nên rất mong nhận được sự chia sẻ của bạn.

Code C/C++

#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;
}