信息学奥赛一本通 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;
}