0

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

我们有一个高度为 h 和宽度为 w 的网格。网格中填充了字符“#”和“.”。Octothorps 代表土地，圆点代表水。保证网格的第一行和最后一行和最后一列都是点。相连的章鱼形成可以有湖泊的岛屿，每个湖泊也可以有岛屿，这些岛屿可以有湖泊等等......每个岛屿都有一个度数，定义为必须跨越的湖泊数量才能到达它如果一个人从网格边缘的水开始（这种水被视为海洋，不包括在到达岛屿必须穿过的湖泊数量之外）。在岛屿中找到最大度数。

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

#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。为什么这个程序会占用这么多内存？它可能与递归函数有关吗？如何改进我的内存管理？

4

1 回答 1

-1

int degree[3010][3010];为3010 * 3010 s预留空间int，即超过900万。如果您在 32 位系统上，这意味着您需要 906 万乘以 4 字节 = 36.2 MB 仅用于此数组；在 64 位系统（今天的标准）上，它需要72.5 MB。
为另外两个添加空间，您就会明白为什么程序需要这么多空间。

于 2020-08-26T20:59:22.413 回答