AcWing 1106. 山峰和山谷
本题链接：AcWing 1106. 山峰和山谷
本博客提供本题截图：
本题分析
本题bfs部分和第一个例题一致，都是八方向扩展，用两个for循环即可has_higer是用来判断是否有比这个山高的，有的话返回ture，low ++，has_lower用来判断是否有比这个山矮的，有的话返回true，high ++，注意我们在定义bfs传递值得时候，has_higer和has_lower传递的是地址，所以在bfs中修改这两个值在main中可以改变，我们也可以定义成全局变量，这样就不需要传递地址了
AC代码
#include <cstdio> #include <map> #include <algorithm> #define x first #define y second using namespace std; typedef pair <int, int> PII; const int N = 1010, M = N * N; int g[N][N]; bool st[N][N]; PII q[M]; int n; void bfs(int x1, int y1, bool &has_higher, bool &has_lower) { int hh = 0, tt = 0; q[0] = {x1, y1}; st[x1][y1] = true; while (hh <= tt) { auto 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 (g[i][j] != g[t.x][t.y]) { if (g[i][j] > g[t.x][t.y]) has_higher = true; if (g[i][j] < g[t.x][t.y]) has_lower = true; } else if (!st[i][j]) { q[++ tt] = {i, j}; st[i][j] = true; } } } } int main() { scanf("%d", &n); for (int i = 0; i < n; i ++ ) for (int j = 0; j < n; j ++ ) scanf("%d", &g[i][j]); int high = 0, low = 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) high ++; if (!has_lower) low ++; } printf("%d %d\n", high, low); return 0; }
三、时间复杂度
关于Flood Fill的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
