Блог

Я решаю задачу из школьного конкурса по программированию. Вот краткое описание:

У нас есть сетка высотой h и шириной w. Сетка заполнена символами ‘#’ и ‘.’. Восьмиугольники представляют землю, а точки представляют воду. Гарантируется, что первая и последняя строка и столбец сетки будут состоять из точек. Связанные октоторпы образуют острова, на которых могут быть озера, и каждое озеро также может иметь острова, и на этих островах могут быть озера и так далее… У каждого острова есть градус, который определяется как количество озер, которые нужно пересечь, чтобы добраться до него, если начинать с воды на краях сетки (эта вода рассматривается как море и исключается из числа озер, которые вы должны пересечь, чтобы добраться до острова). Найдите максимальную степень среди островов.

Я запускаю свою программу на школьном сервере и получаю сообщение о превышении лимита памяти, потому что программа предположительно занимает более 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 amp;amp; a[x   1][y] == a[x][y] amp;amp; degree[x   1][y] == -1)
        searchSame(x   1, y, d);

    if(x - 1 >= 0 amp;amp; a[x - 1][y] == a[x][y] amp;amp; degree[x - 1][y] == -1)
        searchSame(x - 1, y, d);

    if(y   1 < w amp;amp; a[x][y   1] == a[x][y] amp;amp; degree[x][y   1] == -1)
        searchSame(x, y   1, d);

    if(y - 1 >= 0 amp;amp; a[x][y - 1] == a[x][y] amp;amp; 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 amp;amp; a[x   1][y] == a[x][y] amp;amp; !visited[x   1][y])
        search(x   1, y, d);
    else if(x   1 < h amp;amp; !visited[x   1][y])
        search(x   1, y, degree[x][y]   1);

    if(x - 1 >= 0 amp;amp; a[x - 1][y] == a[x][y] amp;amp; !visited[x - 1][y])
        search(x - 1, y, d);
    else if(x - 1 >= 0 amp;amp; !visited[x - 1][y])
        search(x - 1, y, degree[x][y]   1);

    if(y   1 < w amp;amp; a[x][y   1] == a[x][y] amp;amp; !visited[x][y   1])
        search(x, y   1, d);
    else if(y   1 < w amp;amp; !visited[x][y   1])
        search(x, y   1, degree[x][y]   1);

    if(y - 1 >= 0 amp;amp; a[x][y - 1] == a[x][y] amp;amp; !visited[x][y - 1])
        search(x, y - 1, d);
    else if(y - 1 >= 0 amp;amp; !visited[x][y - 1])
        search(x, y - 1, degree[x][y]   1);
}

int main()
{
    int mx = 0;
    scanf("%d %d",amp;h,amp;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. Почему эта программа занимает так много памяти? Может быть, это как-то связано с рекурсивными функциями? Как я могу улучшить управление памятью?

int degree[3010][3010]; резервирует пространство для 3010 * 3010 int сек, то есть более 9 миллионов. Если вы используете 32-битную систему, это означает, что вам нужно 9,06 миллионов раз по 4 байта = 36,2 МБ только для этого массива; в 64-битной системе (стандартной на сегодняшний день) для этого требуется 72,5 МБ.
Добавьте место для двух других, и вы поймете, почему программе требуется так много места.