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

2019-11-14 09:53:29

字體：大中小

供稿：網(wǎng)友

Description

　　FGD小朋友特別喜歡爬山，在爬山的時(shí)候他就在研究山峰和山谷。為了能夠讓他對(duì)他的旅程有一個(gè)安排，他想知道山峰和山谷的數(shù)量。給定一個(gè)地圖，為FGD想要旅行的區(qū)域，地圖被分為n*n的網(wǎng)格，每個(gè)格子(i,j) 的高度w( i,j)是給定的。若兩個(gè)格子有公共頂點(diǎn)，那么他們就是相鄰的格子。（所以與(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)）。我們定義一個(gè)格子的集合S為山峰（山谷）當(dāng) 且僅當(dāng)：1.S的所有格子都有相同的高度。2.S的所有格子都聯(lián)通3.對(duì)于s屬于S，與s相鄰的s’不屬于S。都有ws > ws’（山峰），或者ws < ws’（山谷）。你的任務(wù)是，對(duì)于給定的地圖，求出山峰和山谷的數(shù)量，如果所有格子都有相同的高度，那么整個(gè)地圖即是山峰，又是山谷。 Input

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

　　應(yīng)包含兩個(gè)數(shù)，分別表示山峰和山谷的數(shù)量。 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算法的應(yīng)用。但是這個(gè)題用DFS會(huì)爆棧，所以要改寫用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; } } }