Flood Fill Algorithms - Room Area

Question

There is task to calculate the room area in matrix. first inputs are the coordinates of row and column position - the zeros are free space, 1 - are the walls. The problem is that flood fill function gives me Stack overflow exception.

#include<iostream>
#include<conio.h>
using namespace std;

int a[5][5] = { {0,0,1,0,0},
                {0,0,1,0,0},
                {0,0,1,1,1},
                {1,1,1,0,0},
                {0,0,1,0,0},
};

bool vis[5][5] = { {0,0,0,0,0},
                  {0,0,0,0,0},
                  {0,0,0,0,0},
                  {0,0,0,0,0},
                  {0,0,0,0,0},
};
int c = 0;

void flood(int row, int col){
    if(row < 0 || row > 4 || col < 0 || col > 4)
        return;
    if(a[row][col] == 0 && !vis[row][col]){
        c++;
        vis[row][col] = 1;
    }
    flood(row-1, col);
    flood(row+1, col);
    flood(row,col-1);
    flood(row, col+1);
}

int main(){
    int row, column;
    cin>>row>>column;

    flood(row,column);
    cout<< c;

    getch();
return 0;
}

Answer 1

You shouldn't recurse if you hit a field that you already visited.

In your code, that means that hitting the !vis[row][col] clause should prevent further recursive calls to flood. You can achieve that simply by moving them inside the if (or perhaps a bit more clearly, moving everything outside and flipping the condition). This will also prevent the recursion from happening when you hit a wall, but that's also what you want.