BZOJ 1102: [POI2007]山峰和山谷Grz FloodFill 算法

2019-11-11 07:37:34

字體：大中小

來源：轉載

供稿：網友

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 < ws’（山谷）。你的任務是，對于給定的地圖，求出山峰和山谷的數量，如果所有格子都有相同的高度，那么整個地圖即是山峰，又是山谷。 Input

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

　　應包含兩個數，分別表示山峰和山谷的數量。 Sample Input 輸入樣例1

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

解題方法: 裸FloodFill算法的應用。但是這個題用DFS會爆棧，所以要改寫用BFS。

代碼如下：

#include <bits/stdc++.h>using namespace std;const int maxn = 1010;#define pii pair<int, int>#define MP(x, y) make_pair(x, y)int n, ans1, ans2, a[maxn][maxn];bool flag, vis[maxn][maxn];const int dir[8][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, -1}, {-1, 1}};void Floodfill(int x, int y){ vis[x][y] = 1; queue <pii> que; que.push(MP(x, y)); while(!que.empty()){ pii now = que.front(); que.pop(); for(int i = 0; i < 8; i++){ int dx = now.first + dir[i][0]; int dy = now.second + dir[i][1]; if(dx <= 0 || dx > n || dy <= 0 || dy > n) continue; if(a[dx][dy] > a[now.first][now.second]) flag = 0; if(a[dx][dy] == a[now.first][now.second] && !vis[dx][dy]){ vis[dx][dy] = 1; que.push(MP(dx, dy)); } } }}int main(){ scanf("%d", &n); for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ scanf("%d", &a[i][j]); } } for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ if(!vis[i][j]){ flag = 1; Floodfill(i, j); ans1 += flag; } } } for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ a[i][j] = -a[i][j]; } } memset(vis, 0, sizeof(vis)); for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ if(!vis[i][j]){ flag = 1; Floodfill(i, j); ans2 += flag; } } }