[BFS]POI2007 山峰和山谷 grz 解題報告

Ridges and Valleys

Memory limit: 32 MB

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 ridges and 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 of a square. For each field belonging to the square (for ), its height is given.
We say two fields are adjacent if they have a common side or a common vertex (i.e. the field is adjacent to the fields , , , , , , , , provided that these fields are on the map).
We say a set of fields forms a ridge (valley) if:

• all the fields in have the same height,
• the set forms a connected part of the map (i.e. from any field in it is possible to reach any other field in while moving only between adjacent fields and without leaving the set ),
• if and the field is adjacent to , then (for a ridge) or (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.

Task

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

Input

In the first line of the standard input there is one integer () denoting the size of the map. In each of the following lines there is the description of the successive row of the map. In 'th line (for ) there are integers , ..., (), separated by single spaces. These denote the heights of the successive fields of the 'th row of the map.

Output

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

Example

For the input data:

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

the correct result is:

2 1

while for the input data:

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

the correct result is:

3 3

The above figures show the ridges (continuous line) and the valleys (dashed line).
Task author: Zbigniew Czech.

【中文翻譯】

Description

FGD小朋友特別喜歡爬山，在爬山的時候他就在研究山峯和山谷。爲了能夠讓他對他的旅程有一個安排，他想知道山峯和山谷的數量。 給定一個地圖，爲FGD想要旅行的區域，地圖被分爲n*n的網格，每個格子(i,j) 的高度w(i,j)是給定的。 若兩個格子有公共頂點，那麼他們就是相鄰的格子。（所以與(i,j)相鄰的格子有(i−1, j−1),(i−1,j),(i−1,j+1),(i,j−1),(i,j+1),(i+1,j−1),(i+1,j),(i+1,j+1)）。 我們定義一個格子的集合S爲山峯（山谷）當且僅當： 1.S的所有格子都有相同的高度。 2.S的所有格子都聯通 3.對於s屬於S，與s相鄰的s’不屬於S。都有ws>ws’（山峯），或者ws

Input

第一行包含一個正整數n，表示地圖的大小（1<=n<=1000）。接下來一個n*n的矩陣，表示地圖上每個格子的高度。(0<=w<=1000000000)

Output

應包含兩個數，分別表示山峯和山谷的數量。

Sample Input

輸入樣例1
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
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

Sample Output

輸出樣例1
2 1 輸出樣例2
3 3

HINT

Source
POI2007

【題目連結】
衡陽八中OJ
POI官方

【分析】
嘛～水題，不解釋～～用廣度優先搜索(BFS)搜索每一個連通塊，然後看看這個連通塊周圍的高度是不是都比這個連通塊高（低）就行了。
注意一種情況：

2
1 1
1 1

這東西既是又是山谷～所以輸出1，1～

【我的代碼】

0001 /**************************************************************
0002     Problem: 1102
0003     User: zyfworks
0004     Language: C++
0005     Result: Accepted
0006     Time:2048 ms
0007     Memory:8664 kb
0008 ****************************************************************/
0009 
0010 #include <cstdio>
0011 #include <cstdlib>
0012 #include <queue>
0013 #define readfile(str) freopen(str,"r",stdin)
0014 #define outputfile(str) freopen(str,"w",stdout)
0015 #define MAXN 1001
0016 using namespace std;
0017 const int Step[9][2]={{0,0},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};
0018 int Peak=0;/*Mountain Peak*/
0019 int Valley=0;/*Mountain Valley*/
0020 int Map[MAXN][MAXN];
0021 int Used[MAXN][MAXN];
0022 
0023 int N;
0024 void init()
0025 {
0026     scanf("%d\n",&N);
0027     for (int i=1;i<=N;i++)
0028         for (int j=1;j<=N;j++)
0029             scanf("%d",&Map[i][j]),Used[i][j]=false;
0030     return; 
0031 }
0032 
0033 class QUEUE
0034 {
0035 public:
0036     int x,y;
0037 };
0038 
0039 queue<QUEUE>Q;
0040 
0041 void bfs(int x,int y)
0042 {
0043     while(!Q.empty()) {Q.pop();}
0044     int Tp=0,Tv=0;
0045     QUEUE Tmp,Next;
0046     Tmp.x=x,Tmp.y=y;
0047     Q.push(Tmp);
0048     int Tx,Ty,Nx,Ny;
0049     while(!Q.empty())
0050     {
0051         Tmp=Q.front();
0052         Q.pop();
0053         Tx=Tmp.x,Ty=Tmp.y;
0054         Used[Tx][Ty]=true;
0055         for (int i=1;i<=8;i++)
0056         {
0057             Nx=Tx+Step[i][0];
0058             Ny=Ty+Step[i][1];
0059             if(Nx<1 || Nx>N || Ny<1 || Ny>N)
0060                 continue;
0061             if(Map[Nx][Ny]>Map[Tx][Ty])
0062                 Tv++;
0063             if(Map[Nx][Ny]<Map[Tx][Ty])
0064                 Tp++;
0065             if(Map[Nx][Ny]==Map[Tx][Ty] && !Used[Nx][Ny])
0066             {
0067                 Next.x=Nx,Next.y=Ny;
0068                 Used[Nx][Ny]=true;
0069                 Q.push(Next);
0070             }
0071         }
0072     }
0073 
0074     if(Tp==0 && Tv==0)
0075         Peak++,Valley++;
0076 
0077     if(Tp>0 && Tv==0)
0078         Peak++;
0079     if(Tv>0 && Tp==0)
0080         Valley++;
0081 }
0082 
0083 void solve()
0084 {
0085     for (int i=1;i<=N;i++)
0086     {
0087         for (int j=1;j<=N;j++)
0088         {
0089             if(Used[i][j])
0090                 continue;
0091             bfs(i,j);
0092         }
0093     }
0094     printf("%d %d\n",Peak,Valley);
0095 }
0096 
0097 int main()
0098 {
0099     //readfile("grz.in"),outputfile("grz.out");
0100     init();
0101     solve();
0102     return 0;
0103 }