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 Hij so với mặt nước biển (0 <= Hij <= 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
Các 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 đó, tôi 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 tôi 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:
(Các 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 tôi 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 tôi 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 các 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; | |
| } |
Code by: Phạm Văn Lâm