Information
- ID
- 226
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 7
- Tags
- # Submissions
- 41
- Accepted
- 8
- Uploaded By
#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;
}
#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;
}