DT2 - DT3
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: duytoannguyenledh

Nông trang có rất nhiều ngọn đồi núi, để bảo vệ nông trang nông dân HP 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 <= 1000) hàng và M (1 < M <= 1000) 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 <= 10000) 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.

Dữ liệu vào :

          - Dòng thứ nhất chứa hai số nguyên M và N.

          - M dòng tiếp theo là ma trận thể hiện bản đồ nông trại.

Kết quả :

          - Chứa một số nguyên duy nhất là số lượng đỉnh đồi.

INP

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ụ:

 

 

 

 

 

 

 

 

 

 

 

Ràng buộc:

          - Có 30% số test ứng với 30% số điểm của bài có 1<M,N<=100.

          - Có 30% số test ứng với 30% số điểm của bài có 100<M,N<=500.

          - Có 40% số test ứng với 40% số điểm của bài có 500<M,N<=1000.

Ví dụ

Back to Top