Task DescriptionDiscussion (0)
Hint:
There are three peaks: The one with height 4 on the left top, one of the points with height 2 at the bottom part, and one of the points with height 1 on the right top corner.
Task :: Guarding the Farm
The farm has many hills upon which Farmer John would like to place guards to ensure the safety of his valuable milk-cows.
He wonders how many guards he will need if he wishes to put one on top of each hill. He has a map supplied as a matrix of integers; the matrix has N (1 < N ≤ 700) rows and M (1 < M < 700) columns. Each member of the matrix is an altitude H_ij (0 ≤ H_ij ≤ 10,000). Help him determine the number of hilltops on the map.
A hilltop is one or more adjacent matrix elements of the same value surrounded exclusively by either the edge of the map or elements with a lower (smaller) altitude. Two different elements are adjacent if the magnitude of difference in their X coordinates is no greater than 1 and the magnitude of differences in their Y coordinates is also no greater than 1.
He wonders how many guards he will need if he wishes to put one on top of each hill. He has a map supplied as a matrix of integers; the matrix has N (1 < N ≤ 700) rows and M (1 < M < 700) columns. Each member of the matrix is an altitude H_ij (0 ≤ H_ij ≤ 10,000). Help him determine the number of hilltops on the map.
A hilltop is one or more adjacent matrix elements of the same value surrounded exclusively by either the edge of the map or elements with a lower (smaller) altitude. Two different elements are adjacent if the magnitude of difference in their X coordinates is no greater than 1 and the magnitude of differences in their Y coordinates is also no greater than 1.
INPUT:
* Line 1: Two space-separated integers: N and M
* Lines 2..N+1: Line i+1 describes row i of the matrix with M space-separated integers: H_ij
* Line 1: Two space-separated integers: N and M
* Lines 2..N+1: Line i+1 describes row i of the matrix with M space-separated integers: H_ij
OUTPUT:
* Line 1: A single integer that specifies the number of hilltops
* Line 1: A single integer that specifies the number of hilltops
Input:
Output:
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
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
Output:
3
Hint:
There are three peaks: The one with height 4 on the left top, one of the points with height 2 at the bottom part, and one of the points with height 1 on the right top corner.
Submit Solution
Available Languages
Task info
| Name: | Guarding the Farm |
| Time: | 1 sec. |
| Memory: | 32 MB |
| #Tests: | 15 |
| AddedBy: | Gorgi... |
| Source: | Elite 2008 November Competition USACO |
Task Ratings
| Difficulty: | 3.5 (6 votes) |
| Quality: | 4.2 (5 votes) |
Acceptance Rate
Recent Submissions
Fastest Solutions
| User | Time |
|---|---|
| A.Armin | 0.255 s. |
| nikolakatic | 0.435 s. |
| MatejGradicek | 0.465 s. |
| matteo123 | 0.495 s. |
| FilipKeri | 0.6 s. |
| zermx_011 | 0.675 s. |
| PetarV | 0.72 s. |
| crusader | 0.735 s. |
| khaz.madan | 0.735 s. |
| tobing | 0.75 s. |
Solved By
Home
Training
Competitions
Forum
FAQ