信息学奥赛一本通 1454：山峰和山谷

【题目链接】

ybt 1454：山峰和山谷

【题目考点】

1. 网格图：连通块 深搜 广搜

【解题思路】

相同高度的相邻多个位置构成一个连通块。
设二维数组标记每个位置是否已访问过。
尝试从每个位置出发进行搜索（可以进行深搜或广搜）。
如果该位置没有访问过，则从该位置开始进行搜索。
访问某位置(sx,sy)后，尝试访问其周围（上、下、左、右、左上、右上、左下、右下）的位置(x,y)，(x,y)位置需要保证在地图范围内且没有访问过。

• 如果(x,y)位置的高度与(sx,sy)位置的高度相同，那么从(x,y)位置出发继续进行搜索。
• 如果(x,y)位置的高度与(sx,sy)位置的高度不同，(x,y)位置就是(sx,sy)位置所属的连通块周围的一个位置。
  • 如果(x,y)位置比(sx,sy)位置更高，则记录周围存在比当前连通块更高的的位置。
  • 如果(x,y)位置比(sx,sy)位置更矮，则记录周围存在比当前连通块更矮的的位置。

当前连通块搜索结束后，

• 如果周围只存在比当前连通块更高的位置，则当前连通块是山谷，山谷数量加1。
• 如果周围只存在比当前连通块更矮的位置，则当前连通块是山峰，山峰数量加1。

最后输出山谷和山峰的数量。

【题解代码】

解法1：广搜 连通块

#include<bits/stdc++.h>
using namespace std;
#define N 1005
struct Pair
{
	int x, y;
};
int n, peak, valley, a[N][N], dir[8][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
bool vis[N][N], hasHigher, hasLower;
void bfs(int stx, int sty)
{
	hasHigher = hasLower = false;
	queue<Pair> que; 
	que.push(Pair{stx, sty});
	vis[stx][sty] = true;
	while(!que.empty())
	{
		int sx = que.front().x, sy = que.front().y;
		que.pop();
		for(int i = 0; i < 8; ++i)
		{
			int x = sx+dir[i][0], y = sy+dir[i][1];
			if(x >= 1 && x <= n && y >= 1 && y <= n)
			{
				if(a[sx][sy] == a[x][y] && !vis[x][y])
				{
					vis[x][y] = true;
					que.push(Pair{x, y});
				}
				else if(a[sx][sy] < a[x][y])
					hasHigher = true;
				else if(a[sx][sy] > a[x][y])
					hasLower = true;
			}
		}
	}
	if(hasHigher && !hasLower)//只有比自己高的，没有比自己低的 
		valley++;
	else if(!hasHigher && hasLower)//只有比自己低的，没有比自己高的 
		peak++;
	else if(!hasHigher && !hasLower)//周围没有格子，自己是唯一的，是山峰也是山谷
		valley++, peak++; 
}
int main()
{
	cin >> n;
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= n; ++j)
			cin >> a[i][j];
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= n; ++j) if(!vis[i][j])
			bfs(i, j);
	cout << peak << ' ' << valley;
	return 0;
}

解法2：深搜 连通块

#include<bits/stdc++.h>
using namespace std;
#define N 1005
int n, peak, valley, a[N][N], dir[8][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
bool vis[N][N], hasHigher, hasLower;
void dfs(int sx, int sy)
{
	vis[sx][sy] = true;
	for(int i = 0; i < 8; ++i)
	{
		int x = sx+dir[i][0], y = sy+dir[i][1];
		if(x >= 1 && x <= n && y >= 1 && y <= n)
		{
			if(a[sx][sy] == a[x][y] && !vis[x][y])
				dfs(x, y);
			else if(a[sx][sy] < a[x][y])
				hasHigher = true;
			else if(a[sx][sy] > a[x][y])
				hasLower = true;
		}
	}
}
int main()
{
	cin >> n;
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= n; ++j)
			cin >> a[i][j];
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= n; ++j) if(!vis[i][j])
		{
			hasHigher = hasLower = false;
			dfs(i, j);
			if(hasHigher && !hasLower)//只有比自己高的，没有比自己低的 
				valley++;
			else if(!hasHigher && hasLower)//只有比自己低的，没有比自己高的 
				peak++;
			else if(!hasHigher && !hasLower)//周围没有格子，自己是唯一的，是山峰也是山谷
				valley++, peak++; 
		}
	cout << peak << ' ' << valley;
	return 0;
}