second

这题要判断一个连通块和边上的大小可以用BFS来求解如果使用DFS地图1000*1000直接超时

#include<bits/stdc++.h>
using namespace std; 
int a[5005][5005],n;
bool vis[5005][5005];
struct node{
	long long x,y;
}l,r;
queue<node>q;
int dir[8][2]{1,0,0,1,-1,0,0,-1,-1,-1,1,1,-1,1,1,-1};
int peak,valley;
void bfs(int x,int y){
	q.push({x,y});
	vis[x][y]=1;
	bool high=0,low=0;
	while(q.size()){
		r=q.front();
		q.pop();
		for(int i=0;i<8;i++){
			l.x=r.x+dir[i][0];
			l.y=r.y+dir[i][1];
			if(l.x>=1 && l.x<=n && l.y>=1 && l.y<=n){
				if(a[l.x][l.y]>a[r.x][r.y]){
					high=1;
				}
				else if(a[l.x][l.y]<a[r.x][r.y]){
					low=1;
				}
				else{
					if(!vis[l.x][l.y]){
						q.push({l.x,l.y});
						vis[l.x][l.y]=1;
					}
				}
			}
		}
	}
	if(!high){
		peak++;
	}
	if(!low){
		valley++;
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(!vis[i][j]){
				bfs(i,j);
			}
		}
	}
	cout<<peak<<" "<<valley;
	return 0;
}