AcWing 1106. 山峰和山谷
原题链接
中等
作者:
ZTEG
,
2019-11-08 14:58:21
,
所有人可见
,
阅读 4294
#include<bits/stdc++.h>
using namespace std;
int n,ans1,ans2;
bool f[1005][1005];
int MAP[1005][1005];
struct oppo{
int x,y;
}mi;
queue< oppo > v;
int kx[10]={1,-1,0,0,1,1,-1,-1};
int ky[10]={0,0,1,-1,1,-1,-1,1};
void bfs(int x,int y)
{
bool flag1=0,flag2=0;
int h=MAP[x][y];
f[x][y]=1;
mi.x=x;
mi.y=y;
v.push(mi);
while(v.size())
{
oppo lxl=v.front();
v.pop();
for(int i=0;i<8;i++)
{
int tx=lxl.x+kx[i];
int ty=lxl.y+ky[i];
if(tx<=0||ty<=0||tx>n||ty>n)
continue;
if(MAP[tx][ty]==h&&!f[tx][ty])
{
mi.x=tx;
mi.y=ty;
f[tx][ty]=1;
v.push(mi);
}
else if(MAP[tx][ty]>h)
flag1=1;
else if(MAP[tx][ty]<h)
flag2=1;
}
}
if(!flag1)
ans1++;
if(!flag2)
ans2++;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>MAP[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(!f[i][j])
bfs(i,j);
cout<<ans1<<" "<<ans2<<endl;
return 0;
}
写的很好啊,思路清晰
想问一下,为什么是!flag1 和 !flag2
看这篇
语义上的意思就是
has_higher
和has_lower
dfs为什么会超时呀
这是多爱oppo手机
棒啊