#P3456. [POI 2007] GRZ-Ridges and Valleys

[POI 2007] GRZ-Ridges and Valleys

题目描述

Byteasar loves trekking in the hills. During the hikes he explores all the ridges and valleys in vicinity.

Therefore, in order to plan the journey and know how long it will last, he must know the number of ridgesand valleys in the area he is going to visit. And you are to help Byteasar.

Byteasar has provided you with a map of the area of his very next expedition. The map is in the shape ofa n×nn\times n square. For each field (i,j)(i,j) belonging to the square(for i,j{1,,n}i,j\in \{1,\cdots,n\}), its height w(i,j)w_{(i,j)} is given.

We say two fields are adjacent if they have a common side or a common vertex (i.e. the field (i,j)(i,j) is adjacent to the fields (i1,j1)(i-1,j-1),(i1,j)(i-1,j),(i1,j+1)(i-1,j+1),(i,j1)(i,j-1),(i,j+1)(i,j+1),(i+1,j1)(i+1,j-1),(i+1,j)(i+1,j),(i+1,j+1)(i+1,j+1), provided that these fields are on the map).

We say a set of fields SS forms a ridge (valley) if:

all the fields in SS have the same height,the set SS forms a connected part of the map (i.e. from any field in SS it is possible to reach any other field in SS while moving only between adjacent fields and without leaving the set SS),if sSs\in S and the field sSs'\notin S is adjacent to ss, then ws>wsw_s>w_{s'}(for a ridge) or ws<wsw_s<w_{s'} (for a valley).

In particular, if all the fields on the map have the same height, they form both a ridge and a valley.

Your task is to determine the number of ridges and valleys for the landscape described by the map.

TaskWrite a programme that:

reads from the standard input the description of the map, determines the number of ridges and valleys for the landscape described by this map, writes out the outcome to the standard output.

给定一张地势图,求山峰和山谷的数量

输入格式

In the first line of the standard input there is one integer nn (2n1 0002\le n\le 1\ 000)denoting the size of the map. Ineach of the following nn lines there is the description of the successive row of the map. In (i+1)(i+1)'th line(for i{1,,n}i\in \{1,\cdots,n\}) there are nn integers w(i,1),,w(i,n)w_{(i,1)},\cdots,w_{(i,n)}(0wi1 000 000 0000\le w_i\le 1\ 000\ 000\ 000), separated by single spaces. Thesedenote the heights of the successive fields of the ii'th row of the map.

输出格式

The first and only line of the standard output should contain two integers separated by a single space -thenumber of ridges followed by the number of valleys for the landscape described by the map.

5
8 8 8 7 7
7 7 8 8 7
7 7 7 7 7
7 8 8 7 8
7 8 8 8 8
2 1
5
5 7 8 3 1
5 5 7 6 6
6 6 6 2 8
5 7 2 5 8
7 1 0 1 7
3 3