思路:用一个状态去记录连通块的过程中是否出现过一次大于/小于的数,bool判断最后统计一下
自己的错误:dx,dy以后写的空格大点防止眼花出现错误
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
typedef long long LL;
const int maxn=1010;
int g[maxn][maxn];
int vis[maxn][maxn];
int rfeng=0,rgu=0;
int dx[8]={-1 , -1, -1 , 0, 0, 1 , 1, 1};
int dy[8]={-1 , 0, 1 , -1, 1, -1 , 0, 1};
struct P{
int x;int y;
};
int n;
void bfs(int a,int b,bool& has_higher,bool& has_lower)
{
queue <P>q;
q.push({a,b});
while(!q.empty())
{
P now=q.front();q.pop();
for(int i=0;i<8;i++)
{
int nx=now.x+dx[i];int ny=now.y+dy[i];
if(nx>=0&&nx<n&&ny>=0&&ny<n)
{
if(g[nx][ny]!=g[now.x][now.y])
{
if(g[nx][ny]>g[now.x][now.y]) has_higher=true;
else has_lower=true;
}
else if(!vis[nx][ny]&&g[nx][ny]==g[now.x][now.y])
{
vis[nx][ny]=1;
q.push({nx,ny});
}
}
}
}
}
int main(void)
{
cin.tie(0);std::ios::sync_with_stdio(false);
cin>>n;
///似乎int类输入转一维只能用scanf
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>g[i][j];
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
if(!vis[i][j])
{
bool has_higher=false;bool has_lower=false;
vis[i][j]=1;
bfs(i,j,has_higher,has_lower);
if(!has_higher) rfeng++;
if(!has_lower) rgu++;
}
}
cout<<rfeng<<' '<<rgu<<endl;
return 0;
}
dfs为什么会超时呀
为啥出现一次就可以了 不是要都出现才可以嘛 (山峰是在他周围不存在任何一个比他高的数值)一次怎么满足这个条件
if(!has_higher) rfeng;
if(!has_lower) rgu; 这里为啥要取反了?