为什么这个程序占用太多内存

Question

我正在解决一项高中编程竞赛的任务。这里有一个简短的描述：

我们有一个高度为h、宽度为w的网格。网格中填充了字符"#"one_answers"."。章鱼代表陆地，圆点代表水。保证网格的第一行、最后一行和最后一列都是点。连接的章鱼形成了可以有湖泊的岛屿，每个湖泊也可以有岛屿，这些岛屿可以有湖泊等等…每个岛屿都有一个度数，这个度数被定义为如果从网格边缘的水开始，为了到达它，必须穿过的湖的数量(这种水被视为大海，不包括在到达岛屿所需穿过的湖泊数量中(。找出岛屿之间的最大度数。

我在学校服务器上运行我的程序，我收到了一个超过内存限制的错误，因为该程序据称占用了超过300兆字节的内存。这是程序：

#include <stdio.h>
char a[3010][3010];
int degree[3010][3010];
bool visited[3010][3010];
int h, w;
void searchSame(int x, int y, int d)
{
degree[x][y] = d;
if(x + 1 < h && a[x + 1][y] == a[x][y] && degree[x + 1][y] == -1)
searchSame(x + 1, y, d);
if(x - 1 >= 0 && a[x - 1][y] == a[x][y] && degree[x - 1][y] == -1)
searchSame(x - 1, y, d);
if(y + 1 < w && a[x][y + 1] == a[x][y] && degree[x][y + 1] == -1)
searchSame(x, y + 1, d);
if(y - 1 >= 0 && a[x][y - 1] == a[x][y] && degree[x][y - 1] == -1)
searchSame(x, y - 1, d);
}
void search(int x, int y, int d)
{
visited[x][y] = true;

if(degree[x][y] == -1)
searchSame(x,y,d);
if(x + 1 < h && a[x + 1][y] == a[x][y] && !visited[x + 1][y])
search(x + 1, y, d);
else if(x + 1 < h && !visited[x + 1][y])
search(x + 1, y, degree[x][y] + 1);
if(x - 1 >= 0 && a[x - 1][y] == a[x][y] && !visited[x - 1][y])
search(x - 1, y, d);
else if(x - 1 >= 0 && !visited[x - 1][y])
search(x - 1, y, degree[x][y] + 1);
if(y + 1 < w && a[x][y + 1] == a[x][y] && !visited[x][y + 1])
search(x, y + 1, d);
else if(y + 1 < w && !visited[x][y + 1])
search(x, y + 1, degree[x][y] + 1);
if(y - 1 >= 0 && a[x][y - 1] == a[x][y] && !visited[x][y - 1])
search(x, y - 1, d);
else if(y - 1 >= 0 && !visited[x][y - 1])
search(x, y - 1, degree[x][y] + 1);
}
int main()
{
int mx = 0;
scanf("%d %d",&h,&w);
for(int i = 0; i < h; i++)
scanf("%s",a[i]);
for(int i = 0; i < h; i++)
{
for(int j = 0; j < w ; j++)
degree[i][j] = -1;
}   
search(0,0,1);
for(int i = 0; i < h; i++)
{
for(int j = 0; j < w ; j++)
{
if(degree[i][j] > mx)
mx = degree[i][j];
}
}
printf("%d",mx/2 - 1);
}

h和w的值在3到3000之间。为什么这个程序占用这么多内存？它可能和递归函数有关吗？如何改进我的内存管理？

Answer 1

int degree[3010][3010];为3010*3010个int预留空间，即超过900万个。如果您使用的是32位系统，这意味着仅此阵列就需要906万乘以4字节=36.2 MB；在64位系统(目前的标准(上，它需要72.5 MB
添加其他两个的空间，您就会明白为什么程序需要这么多空间。