信息学奥赛一本通T1454-山峰和山谷

解题思路:

根据题目描述

1、没有比它高的叫山峰

2、没有比它矮的叫山谷

3、还存在又比它高，又比它矮的不算山峰也不算山谷

步骤：

找到高度一致的连通块，若该连通块周围

        没有存在比它高的则该连通块叫山峰

        没有存在比它矮的则该连通块叫山谷

参考代码:

#include <iostream>
#include <queue>
#define x first
#define y second
using namespace std;

typedef pair<int, int> PII;

const int N = 1010;

int n, w[N][N], vis[N][N];
queue<PII> q;

void bfs(int x, int y, bool & has_higher, bool & has_lower)
{
	q.push({x, y});
	vis[x][y] = 1;
	while (!q.empty())
	{
		PII p = q.front();
		q.pop();
		for (int i = p.x - 1; i <= p.x + 1; i++)
			for (int j = p.y - 1; j <= p.y + 1; j++)
			{
				if (i == p.x && j == p.y) continue;
				if (i < 1 || i > n || j < 1 || j > n) continue;
				if (w[i][j] != w[p.x][p.y])
				{
					if (w[i][j] > w[p.x][p.y]) has_higher = false; // 周围的高说明当前不是山峰 
					else has_lower = false; // 周围的低说明当前不是山谷 
				}
				else if (!vis[i][j]) // 把相同高度的加入到队列 
				{
					vis[i][j] = 1;
					q.push({i, j});
				}
			}
	}
}

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			cin >> w[i][j];
	int peak = 0, valley = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (!vis[i][j])
			{
				bool has_higher = true, has_lower = true;
				bfs(i, j, has_higher, has_lower);
				if (has_higher) peak++;
				if (has_lower) valley++;
			}
	cout << peak << ' ' << valley << endl;
	return 0;
}