评测记录:link
//连通块
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
const int MAXN = 1050;
int n;
int w[MAXN][MAXN];
bool used[MAXN][MAXN];
struct point{
int x_;
int y_;
};
queue<point>q;
int dx[9] = {0,1,0,-1,1,-1,0,-1,1};
int dy[9] = {0,1,1,1,-1,-1,-1,0,0};
//八连通
int fg,ff;
//非谷,非峰
int a;
void bfs(int x,int y){
if(used[x][y]){
//在其他连通块中处理过
return ;
}
bool srch[MAXN][MAXN];
memset(srch,false,sizeof(srch));
srch[x][y] = true;
a++;
used[x][y] = true;
point tmp;
tmp.x_ = x;
tmp.y_ = y;
q.push(tmp);
bool flag1,flag2;
//是峰?是谷?
flag1 = flag2 = true;
while(!q.empty()){
point b;
b = q.front();
q.pop();
for(int i = 1;i<=8;i++){
point c;
c.x_ = b.x_ + dx[i];
c.y_ = b.y_ + dy[i];
if(c.x_<=0||c.x_>n||c.y_<=0||c.y_>n){
continue;
}
if(srch[c.x_][c.y_]){
continue;
}
if(w[c.x_][c.y_]==w[b.x_][b.y_]){
q.push(c);
//连通块设定
used[c.x_][c.y_] = true;
srch[c.x_][c.y_] = true;
}
else{
if(w[c.x_][c.y_]>w[b.x_][b.y_]){
//不是山峰
flag1 = false;
}
else{
flag2 = false;
}
}
}
}
if(flag1==false){
ff++;
}
if(flag2==false){
fg++;
}
return ;
}
void method_1(){
scanf("%d",&n);
for(int i = 1;i<=n;i++){
for(int j = 1;j<=n;j++){
scanf("%d",&w[i][j]);
}
}
fg = ff = 0;
a = 0;
memset(used,false,sizeof(used));
for(int i = 1;i<=n;i++){
for(int j = 1;j<=n;j++){
bfs(i,j);
}
}
int f,g;
g = a - fg;
f = a - ff;
printf("%d %d",f,g);
return ;
}
int main(){
method_1();
return 0;
}
应该是memset(srch,0,sizeof(srch))爆了。 求助