Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

NKGUARD - Bảo vệ nông trang

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/nkguard


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

Dữ liệu

* 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

Kết quả

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

Ví dụ

Dữ liệu:
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

Kết quả:
3

Được gửi lên bởi:Phong
Ngày:2008-11-11
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:USACO November 2008

hide comments
2014-06-13 03:55:33 Uzumaki Naruto
sadasd
2014-06-05 07:13:10 Thcs Ðặng Chánh Kỷ
1 code Ac( lâu không code Đồ thị code lại bài này lấy cảm giác) DFS là ac
2014-05-11 07:00:41 Duc M. Pham
DFS trâu cũng AC :)) O(8*n*m)

Last edit: 2014-05-11 07:02:25
2014-02-15 17:05:00 Silver Rayleigh
bài này BFS hoặc DFS cũng đc

Last edit: 2014-02-15 17:17:39
2014-01-23 16:42:47 Ðỗ Quốc Tuấn
Làm sao BFS đc? Tìm vùng liên thông đâu mà BFS?
2013-07-25 11:34:37 Bitagi97
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.