[数据结构与算法]AcWing 1106 山峰和山谷 题解（BFS）

AcWing 1106 山峰和山谷
BFS的应用题，新学到的比较连通块和边界的方法，还有就是注意山谷和山峰的has_higher和has_lower的实际意义，别把山谷和山峰搞错了

#include<bits/stdc++.h>

using namespace std;

const int N = 1010;

#define x first
#define y second

typedef pair<int, int>PII;

int n;
PII q[N * N];
bool st[N][N];
int h[N][N];

void bfs(int sx, int sy, bool& has_higher, bool& has_lower){
	st[sx][sy] = true;
	int hh = 0, tt = 0;
	q[0] = {sx, sy};
	
	while(hh <= tt){
		PII t = q[hh ++ ];
		for(int i = t.x - 1; i <= t.x + 1; i ++ ){
			for(int j = t.y - 1; j <= t.y + 1; j ++ ){
				if(i == t.x && j == t.y) continue;
				if(i < 0 || i >= n || j < 0 || j >= n) continue;
				if(h[i][j] != h[t.x][t.y]){
					if(h[i][j] > h[t.x][t.y]) has_higher = true;
					else has_lower = true;
				}
				else if(!st[i][j]){
					st[i][j] = true;
					q[ ++ tt] = {i, j};
				} 
			}
		}
	}
}

int main()
{
	cin>>n;
	for(int i = 0; i < n; i ++ ){
		for(int j = 0; j < n; j ++ ){
			cin>>h[i][j];
		}
	}
	
	int hhh = 0, vvv = 0;
	for(int i = 0; i < n; i ++ ){
		for(int j = 0; j < n; j ++ ){
			if(!st[i][j]){
				bool has_higher = false, has_lower = false;
				bfs(i, j, has_higher, has_lower);
				if(!has_higher) hhh ++ ;
				if(!has_lower) vvv ++ ;
			}
		}
	}	
	cout<<hhh<<' '<<vvv<<endl;
	return 0;
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖