山峰和山谷 Ridges and Valleys

题目描述

思路

一开始看这道题目，也不是很会，谁会把统计之类的问题和bfs联系在一起，没有开始的状态，没有结束的状态，题目中连一个最短之类的词也没有出现。

然后统计嘛，题目中说了方格高度都相同，就把周围的点都看一遍和这个点高度相同的就入队，把高度相同的点都打上浏览的标记。看的过程中，既有比它小的，也有比它大的，那么这种高度的点就不是我们要统计的答案，只有比它小的，或只有比它大的，那么就是我们要统计的。可以设置两个标记，标记看的过程中有没有比它小的，比它大的。

然后就是只有一个高度的时候，因为两个标记都不满足，那么都加1。

然后就是这种题目感觉dfs和bfs都可以做，好像还有一种洪泛法的方法也可以解决。

然后就是抱怨一下bfs有套路，比起dfs要简单，dfs写起来容易，但是怎么表示每一层的状态就比较难，再加上剪枝之类的，qwq······

代码

#include <cstdio>

#include <cstring>

#include <queue>

int n;

int mp[1005][1005], vis[1005][1005], obs[1005][1005];

int dirx[] = {0, -1, -1, -1, 0, 1, 1, 1, 0};

int diry[] = {0, -1,  0,  1, 1, 1, 0,-1,-1};

struct Node {

	int x, y;

} tmp, cur;

std::queue<Node> q;

int lows, highs;

inline int read() {

	int s = 0, f = 1;

	char ch = getchar();

	while (ch < '0' || ch > '9') ch = getchar();

	while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();

	return s * f;

}

bool valid(int x, int y) {

	if (x < 1 || x > n) return false;

	if (y < 1 || y > n) return false;

	return true;

}

void bfs(int x, int y) {

	while (!q.empty()) q.pop();

	tmp.x = x, tmp.y = y;

	q.push(tmp);

	vis[x][y] = 1;

	int z = mp[x][y];

	bool low = false, high = false;

	while (!q.empty()) {

		cur = q.front();

		q.pop();

		for (int i = 1; i <= 8; ++i) {

			tmp.x = cur.x + dirx[i];

			tmp.y = cur.y + diry[i];

			if (valid(tmp.x, tmp.y)) {

				int tz = mp[tmp.x][tmp.y];

				if (tz < z) low = true;

				if (tz > z) high = true;

				if (tz == z && !vis[tmp.x][tmp.y]) {

					q.push(tmp);

					vis[tmp.x][tmp.y] = 1;

				}

			}

		}

	}

	if (!low) lows++;

	if (!high) highs++;

}

int main() {

	n = read();

	for (int i = 1; i <= n; ++i) {

		for (int j = 1; j <= n; ++j) {

			mp[i][j] = read();

		}

	}

	for (int i = 1; i <= n; ++i) {

		for (int j = 1; j <= n; ++j) {

			if (!vis[i][j]) bfs(i, j);

		}

	}

	printf("%d %d", highs, lows);

	return 0;

}

巴特西

山峰和山谷 Ridges and Valleys

题目描述

思路

代码

最新文章

热门文章