|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
const int N = 1010;
|
|
|
|
|
|
// 通过了 20/22个数据
|
|
|
int n;
|
|
|
bool st[N][N];
|
|
|
int h[N][N];
|
|
|
/*
|
|
|
# 不同操作系统默认栈的大小
|
|
|
Linux默认栈空间的大小为8MB，通过命令ulimit -s来设置
|
|
|
在Windows下，栈的大小是2MB
|
|
|
|
|
|
# 原因分析
|
|
|
每进行一次递归，都会在栈上多加一层，所以递归太深的话会出现数据溢出的错误。函数调用层次过深，每调用一次，函数的参数、
|
|
|
局部变量等信息就压一次栈。
|
|
|
|
|
|
n=1000 n*n=1e3*1e3=1e6
|
|
|
sx,sy 每个int 4byte,所以共8 byte
|
|
|
bool has_higher,has_lower 各占1个byte ，所以共2byte
|
|
|
1e6*10=1e7 byte = 1e7/1024 kb=9,765.625 kb = 9.53mb
|
|
|
|
|
|
如果不加上 has_higher,has_lower，就是
|
|
|
1e6*8= 8e6/1024 kb=7,812.5kb = 7.6mb
|
|
|
|
|
|
因AcWing的评测机是GCC搭建在Linux环境中，所以栈的空间默认是8MB（我猜的，不对Y总别骂我~），也就是我们的运气好，采用全局的has_higher,
|
|
|
has_lower刚刚好通过这组测试数据，如果再多一点，一样是会挂掉的，这个是递归与栈的本质造成，这时只能采用bfs进行Flood Fill
|
|
|
|
|
|
# 写给AcWing
|
|
|
一般来说，评测时的栈空间限制等于内存限制。但系统默认的栈空间往往较小，有时会出现官方评测时正常运行，而本地测试时爆栈的情况。这时候就需要对栈空间进行更改。
|
|
|
现在看来AcWing的栈空间是默认的8MB，而不是CCF官方的栈空间限制等于内存限制，不知道y总是出于什么考虑。
|
|
|
参考链接：https://studyingfather.blog.luogu.org/noi-technical-faq
|
|
|
|
|
|
|
|
|
# 解决办法：
|
|
|
* 如果递归的层次较多，尽量避免dfs函数的参数个数，防止递归太深导致MLE出现
|
|
|
* 避开dfs,采用bfs即可解决，此时内存是在堆上分配的，可以使用3GB或以上
|
|
|
|
|
|
*/
|
|
|
void dfs(int sx, int sy, bool &has_higher, bool &has_lower) {
|
|
|
st[sx][sy] = true;
|
|
|
for (int x = sx - 1; x <= sx + 1; x++) {
|
|
|
for (int y = sy - 1; y <= sy + 1; y++) {
|
|
|
if (x <= 0 || x > n || y <= 0 || y > n) continue;
|
|
|
if (h[sx][sy] != h[x][y]) { // 高度不相等
|
|
|
if (h[sx][sy] < h[x][y]) has_higher = true;
|
|
|
if (h[sx][sy] > h[x][y]) has_lower = true;
|
|
|
} else { // 高度相等
|
|
|
if (st[x][y]) continue;
|
|
|
st[x][y] = true;
|
|
|
dfs(x, y, has_higher, has_lower);
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
int vally, peak;
|
|
|
int main() {
|
|
|
for (int i = 1; i <= n; i++)
|
|
|
for (int j = 1; j <= n; j++)
|
|
|
cin >> h[i][j];
|
|
|
|
|
|
for (int i = 1; i <= n; i++) {
|
|
|
for (int j = 1; j <= n; j++) {
|
|
|
if (!st[i][j]) {
|
|
|
bool has_higher = false, has_lower = false;
|
|
|
dfs(i, j, has_higher, has_lower);
|
|
|
if (has_higher && has_lower) continue;
|
|
|
if (has_higher) vally++;
|
|
|
if (has_lower) peak++;
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
|
|
|
// 对于不存在山峰+山谷的一马平地，山峰山谷都输出1
|
|
|
if (peak == 0 && vally == 0) peak = 1, vally = 1;
|
|
|
printf("%d %d\n", peak, vally);
|
|
|
return 0;
|
|
|
} |
