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
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
解题方法: 裸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; } } } PRintf("%d %d/n", ans1, ans2); return 0;}新闻热点
疑难解答
