TOP - Đỉnh đồi
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: admin

Đồn điền trà của gia đình Tý nằm trên địa hình có nhiều ngọn đồi, để bảo vệ đồn điền gia đình giao cho Tý tính toán số người cần thiết để canh gác trên các ngọn đồi này.
Vấn đề là 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. Tý có bản đồ của đồn điền là một ma trận gồm N hàng và M cột. Mỗi phần tử của ma trận có độ cao Hij so với mặt nước biển là 0 của ô (i,j). Hãy giúp Tý 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. 

Dữ liệu vào: đọc từ tập tin văn bản TOP.INP có cấu trúc: 

- Dòng đầu chứa 2 số nguyên N, M cách nhau ít nhất một khoảng trắng (1 < N ≤ 100), (1 < M ≤ 70);

- N dòng tiếp theo mỗi dòng là M số nguyên mô tả độ cao Hij theo thứ tự của ma trận (0 ≤ Hij ≤  10000). 

Kết quả: Xuất ra tập tin văn bản TOP.OUT một số N duy nhất là số đỉnh đồi tìm được.

Ví dụ:

TOP.INP TOP.OUT
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
3

Ví dụ

Giải thích:
Có 3 đỉnh đồi, 1 đỉnh đồi có độ cao 4 là ô nằm ở góc trên bên trái, 1 đỉnh đồi là các ô có độ cao 2 ở phía dưới bản đồ và đỉnh đồi còn lại là các ô có độ cao 1 ở góc phải bản đồ (tô xám).


Đề Thi HSG Tin 9 TPHCM 2017

Back to Top