Why does this program take too much memory?

Question

I'm solving a task from a high school programming competition. Here's a short description:

We have a grid with height h and width w. The grid is filled with chars '#' and '.'. Octothorps represent land and dots represent water. It is guarranted that the first and last row and column of the grid will be all dots. Connected octothorps form islands which can have lakes and every lake can also have islands and these islands can have lakes and so on... Every island has a degree which is defined as the number of lakes which have to be crossed in order to reach it if one starts from the water on the edges of the grid (this water is regarded as the sea and is excluded from the number of lakes you have to cross to reach an island). Find the maximum degree amongst islands.

I'm running my program on a school server and I'm getting a memory limit exceeded error because the program allegedely takes more than 300 MiB of memory. Here is the program:

#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);
}

Values of h and w range from 3 to 3000. Why does this program take so much memory? Does it maybe have something to do with the recursive functions? How can I improve my memory management?

Answer 1

int degree[3010][3010]; reserves space for 3010 * 3010 ints, that is over 9 million. If you are on a 32bit system, that means you need 9.06 million times 4 bytes = 36.2 MB just for this array; on a 64bit system (standard today), it needs 72.5 MB.
Add the space for the other two, and you'll see why the program needs that much space.