The Greatest Peaks
The Royal Army is setting up defenses and they asked you, the Royal Engineer, to help them. They're looking to identify the dominant peaks and areas near the border. Can you help them?
Details
You are given a square map of altitudes of different areas. A peak is a cell surrounded by lower values. A peak's area is the area controlled by that peak. Cells that can be reached by continuously descending (in 4 directions) from a peak are controlled by that peak. A cell that can be reached by descending from more than one cell belongs to the area of the the higher-value cell. Can you identify the smallest and largest areas in each grid?
Input/Output
The first number of input contains the number of test cases. Each tests cases consists of a number N followed by the altitude map of the area, an N*N square of integer altitudes.
Map out the grid into different areas and then print out the size of the smallest area and the size of the largest area.
Guideline
Grids can also be searched with Graph-Search Techniques. Identify the cells to search from to form a map of the area...
Sample Cases
Full Sample Input:
3 3 9 8 5 5 6 3 8 4 1 2 8 12 9 3 4 2 6 9 11 7 8 9 8 6 7 12 9 10 7 6 4
The breakdown of each case is shown below.
Case 1
Input
3 9 8 5 5 6 3 8 4 1
Output
3 6
Explanation
The top 9 and bottom 8 are peaks. The 2 areas are:
A A A A A A B B B
Case 2
Input
2 8 12 9 3
Output
1 3
Explanation
The 2 areas are:
A A B A
Case 3
Input
4 2 6 9 11 7 8 9 8 6 7 12 9 10 7 6 4
Output
3 9
Explanation
The 3 areas are:
B A A A B B B A C B B B C C B B
11, 12 and 10 are peaks (respectively in A, B, and C)
Challenge
Print out the smallest and largest area in each grid
Please sign in or sign up to submit answers.
Alternatively, you can try out Learneroo before signing up.
Comments
Rupesh
Dec 18, 10:31 AMI have a doubt ! In this Output
Input:
4
2 6 9 11
7 8 9 8
6 7 12 9
10 7 6 4
Output(given as) :
B A A A
B B B A
C B B B
C C B B
Can anyone explain the output of this case please?
Rupesh
Dec 18, 10:38 AMIf 11 is the peak element then how come 6,9 and 8 which is marked as A in output is treated
a areas of peak element. Can anyone could please give me a example ?
Learneroo
Dec 21, 8:10 PM9 and 8 can each be reached by going down from 11 so they're part of Area A. Similarly the 6 on top can be reached by going down from the 9, so it also ends up as part of A.
Alvaro Sanchez Diaz
May 11, 10:56 AMWhy does the top 6 ends up beaing part of A and not B?
@Learneroo Could you please explain in detail how the areas are determined in the last example? I can't figure out how the top 2, 7, and 8 are reached by the 12 peak.
Cells that can be reached by continuously descending (in 4 directions) from a peak are controlled by that peak.
A cell that can be reached by descending from more than one cell belongs to the area of the the higher-value cell
That would leave us with:
Peaks:
10, 11, 12
Step 1?
Step 2?
How?
Thank you for your help!
Learneroo
May 11, 6:31 PMWhen a cell is surrounded by multiple cells of higher values, it joins the area of the higher valued cell (regardless of who's peak is higher). It might be easier to work from the small cells back to the peaks, instead of from the peaks down.
So the 2 could be controlled by the 6 or 7, but it joins the 7 since 7>6. The path then continues from 7 -> 8 -> 9 -> 12.