# 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.

• #### Rupesh

I 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

If 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

9 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

Why 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.

• #### Learneroo

When 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.