解题思路:
根据题目描述
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; }
0.0分
24 人评分
WU-C语言程序设计教程(第三版)课后习题11.11 (C++代码)(想学链表的可以看看)浏览:1357 |
2005年春浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:648 |
剪刀石头布 (C语言代码)浏览:752 |
IP判断 (C语言代码)浏览:763 |
C语言考试练习题_一元二次方程 (C语言代码)浏览:576 |
1012题解浏览:869 |
2006年春浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:345 |
数列问题 (C语言代码)浏览:1022 |
筛排处理 (C语言代码)浏览:787 |
JAM计数法 (C语言代码)浏览:671 |