2 solutions
-
-1
#include<bits/stdc++.h> using namespace std; typedef pair<int,int> PII; #define x first #define y second const int N=1010; bool st[N][N]; int dx[]={0,1,0,-1,1,1,-1,-1}; int dy[]={1,0,-1,0,1,-1,1,-1}; int g[N][N]; int main() { int n; cin>>n; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { cin>>g[i][j]; } } int a=0,b=0; //山峰和山谷的数目 for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(!st[i][j]) { queue<PII> q; q.push({i,j}); st[i][j]=1; int h=0,l=0; while(q.size()) { PII t=q.front(); q.pop(); for(int k=0;k<8;k++) { int tx=t.x+dx[k],ty=t.y+dy[k]; if(tx<=0||tx>n||ty<=0||ty>n) continue; if(g[tx][ty]!=g[t.x][t.y]) //不相同 { if(g[t.x][t.y]<g[tx][ty]) l=1; //存在某个点比当前点高(一定不是山峰) else h=1; // 存在某个点比当前点底(一定不是山谷) } else if(!st[tx][ty]) { st[tx][ty]=1; q.push({tx,ty}); } } } if(!h) b++; //可以是山谷 if(!l) a++; //可以是山峰 } } } cout<<a<<" "<<b; return 0; }
-
-2
#include using namespace std; typedef pair<int,int> PII; #define x first #define y second const int N=1010; bool st[N][N]; int dx[]={0,1,0,-1,1,1,-1,-1}; int dy[]={1,0,-1,0,1,-1,1,-1}; int g[N][N]; int main() { int n; cin>>n; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { cin>>g[i][j]; } } int a=0,b=0; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(!st[i][j]) { queue<PII> q; q.push({i,j}); st[i][j]=1; int h=0,l=0; while(q.size()) { PII t=q.front(); q.pop(); for(int k=0;k<8;k++) { int tx=t.x+dx[k],ty=t.y+dy[k]; if(tx<=0||tx>n||ty<=0||ty>n) continue; if(g[tx][ty]!=g[t.x][t.y]) { if(g[t.x][t.y]<g[tx][ty]) l=1; else h=1; } else if(!st[tx][ty]) { st[tx][ty]=1; q.push({tx,ty}); } } } if(!h) b++; if(!l) a++; } } } cout<<a<<" "<<b; return 0; }
- 1
Information
- ID
- 226
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 7
- Tags
- # Submissions
- 27
- Accepted
- 5
- Uploaded By