0

This is my solution, which receives a heap buffer overflow (out of bounds):

void FFHelper(vector<vector<int>>& image, int i, int j, int newColor, int oldColor)
{
    static int m = image.size(); 
    static int n = image[0].size();

    if (i < 0 || j < 0 
        || i >= m || j >= n 
        || image[i][j] != oldColor) 
    {
       return;
    }

    image[i][j] = newColor;

    FFHelper(image, i+1, j, newColor, oldColor);
    FFHelper(image, i-1, j, newColor, oldColor);
    FFHelper(image, i, j+1, newColor, oldColor);
    FFHelper(image, i, j-1, newColor, oldColor);
}

vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color)
{
    FFHelper(image, sr, sc, color, image[sr][sc]);

    return image;
}

where it is guaranteed that 0 <= sr < m and 0 <= sc < n where image is m x n.

This is a code that receives no buffer overflow:

void dfs(vector<vector<int>>& image, int i, int j, int val, int newColor)
{
    if(i < 0 || i >= image.size() 
       || j < 0 || j>= image[0].size() 
       || image[i][j] == newColor || image[i][j] != val)
    {
        return;
    }

    image[i][j] = newColor;

    dfs(image, i - 1, j, val, newColor);
    dfs(image, i + 1, j, val, newColor);
    dfs(image, i, j - 1, val, newColor);
    dfs(image, i, j + 1, val, newColor);
}
    
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, 
int newColor)
{
    int val = image[sr][sc];

    dfs(image, sr, sc, val, newColor);

    return image;
}

What is the difference? I seriously don't see it. Someone from codereview.stackexchange suggested I post here.

Adam
  • 2,726
  • 1
  • 9
  • 22
user20896951
  • 35
  • 5
  • 7
    In the fist version you use `static` variables to hold the width and height. This will break if you call `floodFill` the 2nd time, with an image smaller than the first (because the `static`s will not be updated). – wohlstad Jan 03 '23 at 06:25
  • 1
    `j+1` can go out of bounds in both. and don't use static Also don't use `using namespace std;`. And know that when using 2D vectors for images each line can end up in a total different part of memory (which can be a perfomance issue). – Pepijn Kramer Jan 03 '23 at 06:25
  • @PepijnKramer I think that this issue by itself (the `j+1` issue) will not cause a problem, because the function will exit on the first `if` and will not do the out-of-bounds access. – wohlstad Jan 03 '23 at 06:28
  • 1
    @wohlstad I see that now too, it will just do an unecessary extra recurse call which will then fail. It is just that from code review experience I trigger on loops with `<= `or `>=` in them. It is uncommon and thus surprising. – Pepijn Kramer Jan 03 '23 at 06:31
  • OP, you may in the future use a debugger to identify issues like this :) – madhur4127 Jan 03 '23 at 06:33
  • I see @wohlstad . Before i was passing in the variables `m` and `n` recursively as arguments, but this led to stack overflow, probably because they end up in caller-saved registers. – user20896951 Jan 03 '23 at 06:33
  • Is there a way to avoid that call to `.size()` on every recursive iteration? That was what I was hoping with the `static` variables. – user20896951 Jan 03 '23 at 06:36
  • 1
    @user20896951why do you want to avoid that ? `std::vector::size` is O(1) and typically very fast. It does not require to traverse the vector. – wohlstad Jan 03 '23 at 06:38
  • @user20896951 As you get more experienced, you'll realise that your solution (using static variables) is worse than the 'problem' it is solving. – john Jan 03 '23 at 06:42
  • A stack overflow in recursive functions is usually the result of invalid end conditions. A bug in your if statement for example and has no relation to whether your local variables are static or not. Also try to give your variables better names (width/height, x, y etc.). Also you can query the image size once in your first function and pass that on – Pepijn Kramer Jan 03 '23 at 06:42
  • 2
    If you care about performance, see @PepijnKramer's comment above about keeping the whole image in continuous memory. – wohlstad Jan 03 '23 at 06:43
  • 1
    Just don't use recursion, it doesn't scale well, see https://stackoverflow.com/questions/21865922/non-recursive-implementation-of-flood-fill-algorithm – Alan Birtles Jan 03 '23 at 07:28

0 Answers0