• 山峰和山谷—BFS

    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为山峰（山谷）当且仅当：

     

    • 输入格式

       

      第一行包含一个正整数 n，表示地图的大小。接下来一个 n×n的矩阵，表示地图上每个格子的高度 w。

      输出格式

      共一行，包含两个整数，表示山峰和山谷的数量。

      数据范围：1≤n≤1000,0≤w≤109

      输入样例1：

      1. 5
      2. 8 8 8 7 7
      3. 7 7 8 8 7
      4. 7 7 7 7 7
      5. 7 8 8 7 8
      6. 7 8 8 8 8

      输出样例1：

      2 1

      输入样例2：

      1. 5
      2. 5 7 8 3 1
      3. 5 5 7 6 6
      4. 6 6 6 2 8
      5. 5 7 2 5 8
      6. 7 1 0 1 7

      输出样例2：

      3 3

      样例解释

      样例1：

      样例2：

    我的WA代码

    1. #include 
    2. #define endl '\n'
    3. #define int long long
    4. #define Bug cout<<"---------------------"<
    5. using namespace std;
    6. const int N = 1010;
    7. int mp[N][N];
    8. bool vis[N][N];
    9. int n;
    10. int dx[8] = { 0,0,1,-1,1,-1,-1,1 };
    11. int dy[8] = { 1,-1,0,0,-1,-1,1,1 };
    12. bool in(int x, int y) {
    13. 	return x >= 0 && x < n&& y >= 0 && y < n;
    14. }
    15. int flag;
    16. int dfs(int x, int y) {
    17. 	int now = mp[x][y];
    18. 	vis[x][y] = true;
    19. 	for (int i = 0;i < 8;i++) {
    20. 		int tx = x + dx[i];
    21. 		int ty = y + dy[i];
    22. 		//第一次对周围的判断，如果有大的，则标记为山谷。有小的则是山峰
    23. 		if (in(tx, ty)&&mp[tx][ty] > now&&flag==-1) {
    24. 			flag = 1;
    25. 		}
    26. 		if (in(tx, ty) && mp[tx][ty] < now&&flag==-1) {
    27. 			flag = 2;
    28. 		}
    29. 		//后续如果有违反规律的情况，就return-1；
    30. 		if (in(tx, ty) && flag == 2 && mp[tx][ty] > now) {
    31. 			return -1;
    32. 		}
    33. 		if ( in(tx, ty) && flag == 1 && mp[tx][ty] < now) {
    34. 			return -1;
    35. 		}
    36. 		//探索周围的所有情况；如果相等，就探索。
    37. 		if (!vis[tx][ty] && in(tx, ty) && mp[tx][ty] == now) {
    38. 			dfs(tx, ty);
    39. 		}
    40. 	}
    41. 	return flag;
    42. }
    43. signed main() {
    44. 	ios_base::sync_with_stdio(0);
    45. 	cin.tie(0); cout.tie(0);
    46. 	cin >> n;
    47. 	for (int i = 0;i < n;i++) {
    48. 		for (int j = 0;j < n;j++) {
    49. 			cin >> mp[i][j];
    50. 		}
    51. 	}
    52. 	int mon = 0;int gu = 0;
    53. 	for (int i = 0;i < n;i++) {
    54. 		for (int j = 0;j < n;j++) {
    55. 			//memset(vis, false, sizeof(vis));
    56. 			flag = -1;
    57. 			if (!vis[i][j]) {
    58. 				flag = dfs(i, j);
    59. 			}
    60. 			if(flag==1){
    61. 				gu++;
    62. 			}
    63. 			else if (flag == 2) {
    64. 				mon++;
    65. 			}
    66. 			else if (flag == -1) {
    67. 				continue;
    68. 			}
    69. 		}
    70. 	}
    71. 	cout << mon << ' ' << gu << endl;
    72. 	return 0;
    73. }

    DFS——TLE代码

    1. //山谷和山峰
    2. #include
    3. #include
    4. using namespace std;
    5. const int N=1005;
    6. int n;
    7. bool f[N][N];
    8. int mp[N][N];
    9. bool has_higher,has_lower;
    10. void dfs(int x,int y,bool& has_higher,bool& has_lower){
    11.     f[x][y]=true;
    12.     for(int i=-1;i<=1;i++){
    13.         for(int j=-1;j<=1;j++){
    14.             int nx=x+i;
    15.             int ny=y+j;
    16.             if(nx<0 || nx>=n || ny<0 || ny>=n){
    17.                 continue;
    18.             }
    19.             if(mp[x][y]!=mp[nx][ny]){//高度不相等
    20.                 if(mp[x][y] < mp[nx][ny]){
    21.                     has_higher=true;
    22.                 }
    23.                 if(mp[x][y] > mp[nx][ny]){
    24.                     has_lower=true;
    25.                 }
    26.             }else{//高度相等
    27.                 //has_higher=true;
    28.                 //has_lower=true;
    29.                 if(f[nx][ny]){
    30.                     //已经访问过
    31.                     continue;
    32.                 }
    33.                 f[nx][ny]=true;
    34.                 dfs(nx,ny,has_higher,has_lower);
    35.             }
    36.         }
    37.     }
    38. }
    39. int main(){
    40.     int vally=0,peak=0;
    41.     cin>>n;
    42.     set<int>v;
    43.     for(int i=0;i
    44.         for(int j=0;j
    45.             cin>>mp[i][j];
    46.             v.insert(mp[i][j]);
    47.         }
    48.     }
    49.     if(v.size()==1){
    50.         cout<<1<<' '<<1<
    51.         return 0;
    52.     }
    53.     for(int i=0;i
    54.         for(int j=0;j
    55.             if(!f[i][j]){
    56.                 has_higher=false;
    57.                 has_lower=false;
    58.                 dfs(i,j,has_higher,has_lower);
    59.                 if(has_higher && has_lower){
    60.                     continue;
    61.                 }
    62.                 if(has_higher){
    63.                     vally++;
    64.                 }
    65.                 if(has_lower){
    66.                     peak++;
    67.                 }
    68.             }
    69.         }
    70.     }
    71.     cout<' '<
    72.     return 0;
    73. }

     BFS-AC代码

    1. #include 
    2. #define endl '\n'
    3. #define int long long
    4. using namespace std;
    5. constexpr int N = 1010;
    6. typedef pair<int, int>pii;
    7. int n;
    8. int mp[N][N];
    9. bitset vis[N];
    10. int dx[10] = { 1,-1,0,0,1,1,-1,-1 };
    11. int dy[10] = { 0,0,1,-1,1,-1,-1,1 };
    12. int mon, vall;
    13. bool in(int x, int y) {
    14. 	return x >= 0 && x < n&& y >= 0 && y < n;
    15. }
    16. void bfs(int x,int y,bool&higher,bool&lower) {
    17. 	queueq;
    18. 	vis[x][y] = true;
    19. 	q.push(make_pair(x, y));
    20. 	while (!q.empty()) {
    21. 		pii now = q.front();
    22. 		q.pop();
    23. 		for (int i = 0;i < 8;i++) {
    24. 			int tx = now.first + dx[i];
    25. 			int ty = now.second + dy[i];
    26. 			if (in(tx, ty) && !vis[tx][ty] && mp[tx][ty] == mp[now.first][now.second]) {
    27. 				vis[tx][ty] = true;
    28. 				q.push(make_pair(tx,ty));
    29. 			}
    30. 			else if (in(tx, ty) && mp[tx][ty] > mp[now.first][now.second]) {
    31. 				higher = true;
    32. 			}
    33. 			else if (in(tx, ty) && mp[tx][ty] < mp[now.first][now.second]) {
    34. 				lower = true;
    35. 			}
    36. 		}
    37. 	}
    38. }
    39. signed main() {
    40. 	ios_base::sync_with_stdio(0);
    41. 	cin.tie(0); cout.tie(0);
    42. 	cin >> n;
    43. 	for (int i = 0;i < n;i++) {
    44. 		for (int j = 0;j < n;j++) {
    45. 			cin >> mp[i][j];
    46. 		}
    47. 	}
    48. 	for (int i = 0;i < n;i++) {
    49. 		for (int j = 0;j < n;j++) {
    50. 			if (!vis[i][j]) {
    51. 				bool higher = false;bool lower = false;
    52. 				bfs(i, j,higher,lower);
    53. 				if (!higher && !lower) {
    54. 					mon++, vall++;
    55. 				}
    56. 				else if (!higher&&lower) {
    57. 					mon++;
    58. 				}
    59. 				else if (!lower&&higher) {
    60. 					vall++;
    61. 				}
    62. 			}
    63. 		}
    64. 	}
    65. 	cout << mon << ' ' << vall << endl;
    66. return 0;
    67. }

    —

  • 相关阅读:
    Linux系统之部署Dailynotes个人笔记管理工具登录到Dailynotes首页，输入内容无法保存，如何解决？
    数字化新零售营销模式如何落地？数字化新零售营销功能推荐
    Tomcat总体架构，启动流程与处理请求流程
    Socks5代理IP：保障跨境电商的网络安全
    DGIOT国内首家轻量级物联网开源平台——MQTT接入实战教程
    【C++】设计模式之观察者模式
    leetcode每天5题-Day53-贪心2
    如何在Vim中使用内置的Make命令来编译程序？
    植入“人工心脏”助患者重获“心”生
    【CMU15-445 Part-8】Tree Indexes ii
  • 原文地址：https://blog.csdn.net/m0_72522122/article/details/127637385