复习的时候敲BFS,写P3456,出问题了,请各位大佬指教。QWQ
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
typedef pair <int,int> PII;
int n,a[1010][1010];
bool st[1010][1010];
int xx[10]={-1,-1,-1,0,0,1,1,1};
int yy[10]={-1,0,1,-1,1,-1,0,1};
int bfs(int x,int y){
queue<PII> q;
q.push({x,y});
st[x][y]=1;
int flag=0;//1:山峰;2:山谷 ;3:no
while(q.empty()==false){
PII t=q.front();
q.pop();
for(int i=0;i<8;i++){
int tx=t.first+xx[i];
int ty=t.second+yy[i];
if(tx<=0||tx>n||ty<=0||ty>n){
continue;
}
if(a[tx][ty]<a[t.first][t.second]){
if(flag==2){
flag=3;
}
if(flag==0){
flag=1;
}
}
else if(a[tx][ty]>a[t.first][t.second]){
if(flag==1){
flag=3;
}
if(flag==0){
flag=2;
}
}
else if(a[tx][ty]==a[t.first][t.second]&&st[tx][ty]==0){
st[tx][ty]=1;
q.push({tx,ty});
}
}
}
return flag;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&a[i][j]);
}
}
int sg=0,sf=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(st[i][j]==1){
continue;
}
int flag=bfs(i,j);
if(flag==1){
sf++;
}
if(flag==2){
sg++;
}
}
}
printf("%d %d",sf,sg);
}