2 条题解
-
0
#include<bits/stdc++.h> using namespace std; const int N=1010; int n,h[N][N],w;//w==1谷 , w==2峰 bool vis[N][N]; int dx[8]={-1,-1,-1,0,0,1,1,1}; int dy[8]={-1,0,1,-1,1,-1,0,1}; void dfs(int x,int y) { vis[x][y]=1; //标记当前点已访问 for(int i=0;i<8;i++)//搜索与当前点相邻的8个点 { int xx=x+dx[i],yy=y+dy[i]; if(!(xx>=1&&xx<=n&&yy>=1&&yy<=n))continue; if(h[xx][yy]==h[x][y]&&vis[xx][yy]==0) dfs(xx,yy); else if( (h[xx][yy]<h[x][y]&&w==1) || (h[xx][yy]>h[x][y]&&w==2) ) //周围既有比它高的又有比它低的 则它什么也不是,为-1 w=-1; else if(w==0)//没确定是是峰还是谷,为0。搜到与当前搜索高度不同的点 暂且标记当前搜索区域是峰还是谷 { if(h[xx][yy]<h[x][y])w=2; if(h[xx][yy]>h[x][y])w=1; } } } int main() { scanf("%d",&n); bool bk=1;int v=-1; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { scanf("%d",&h[i][j]); if(v==-1)v=h[i][j]; if(h[i][j]!=v)bk=0; //如果有高度不相同的点 } if(bk){printf("1 1\n");return 0;} memset(vis,0,sizeof(vis)); int a=0,b=0; //a表示山峰个数,b表示山谷个数 for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(vis[i][j]==0)//找到一个没搜过的点开始搜索 { w=0; //w=0表示当前点还没确定是山峰还是山谷 dfs(i,j); if(w==1)a++; else if(w==2)b++; } printf("%d %d\n",b,a); return 0; } -
0
#include<bits/stdc++.h> using namespace std; const int N=1010; int n,h[N][N],w;//w==1谷 , w==2峰 bool vis[N][N]; int dx[8]={-1,-1,-1,0,0,1,1,1}; int dy[8]={-1,0,1,-1,1,-1,0,1}; void dfs(int x,int y) { vis[x][y]=1; //标记当前点已访问 for(int i=0;i<8;i++)//搜索与当前点相邻的8个点 { int xx=x+dx[i],yy=y+dy[i]; if(!(xx>=1&&xx<=n&&yy>=1&&yy<=n))continue; if(h[xx][yy]==h[x][y]&&vis[xx][yy]==0) dfs(xx,yy); else if( (h[xx][yy]<h[x][y]&&w==1) || (h[xx][yy]>h[x][y]&&w==2) ) //周围既有比它高的又有比它低的 则它什么也不是,为-1 w=-1; else if(w==0)//没确定是是峰还是谷,为0。搜到与当前搜索高度不同的点 暂且标记当前搜索区域是峰还是谷 { if(h[xx][yy]<h[x][y])w=2; if(h[xx][yy]>h[x][y])w=1; } } } int main() { scanf("%d",&n); bool bk=1;int v=-1; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { scanf("%d",&h[i][j]); if(v==-1)v=h[i][j]; if(h[i][j]!=v)bk=0; //如果有高度不相同的点 } if(bk){printf("1 1\n");return 0;} memset(vis,0,sizeof(vis)); int a=0,b=0; //a表示山峰个数,b表示山谷个数 for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(vis[i][j]==0)//找到一个没搜过的点开始搜索 { w=0; //w=0表示当前点还没确定是山峰还是山谷 dfs(i,j); if(w==1)a++; else if(w==2)b++; } printf("%d %d\n",b,a); return 0; }
- 1
信息
- ID
- 2755
- 时间
- 2000ms
- 内存
- 64MiB
- 难度
- 6
- 标签
- 递交数
- 22
- 已通过
- 11
- 上传者