CODEWITHSUNDEEP
javascriptarraysfunctionrecursionflood-fill
Charlie Brinley Codd
Charlie Brinley Codd

Reputation: 3

Flood-fill algorithm in Javascript not filling the entire grid when using for loops

I've been working at this all day, and I can't work out why this algorithm doesn't cover the entire grid when starting at position grid[1][1].

I start by setting up the grid and calculating the number of rows and columns in the grid to give me a limit on the edges of the array.

I then call the function, setting position grid[1][1] = 1, calculating the offset and making sure it is not outside the array and making sure the new position has not already been called before calling the function recursively.

I just can't figure out why this isn't working! 

var grid = [[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]];
var cols = grid.length;
var rows = grid[0].length;

floodFill(1, 1)

function floodFill(col, row) {
  grid[col][row] = 1;
  for (c_off = -1; c_off < 2; c_off++) {
    for (r_off = -1; r_off < 2; r_off++) {
      var i = col + c_off;
      var j = row + r_off;
      if (i > -1 && i < cols && j > -1 && j < rows) {
        if (grid[i][j] != 1) {
          floodFill(i, j);
        }
      }
    }
  }
}

grid;

/*
output:
[ [ 1, 1, 1, 1, 1 ],
  [ 1, 1, 1, 1, 1 ],
  [ 1, 1, 1, 1, 1 ],
  [ 1, 1, 1, 1, 0 ],
  [ 1, 1, 0, 0, 0 ] ]

expected output:
[ [ 1, 1, 1, 1, 1 ],
  [ 1, 1, 1, 1, 1 ],
  [ 1, 1, 1, 1, 1 ],
  [ 1, 1, 1, 1, 1 ],
  [ 1, 1, 1, 1, 1 ] ] 
*/

Upvotes: 0

Views: 289

Answers (2)

Itay Maman
Itay Maman

Reputation: 30733

That's because c_off and r_off are not defined as local variables (via the var or let keywords) so they are treated like a global variables which means that a recursive invocation of floodFill() overwrites the values for its calling invocation thereby interfering with the caller's iteration order.

The fix is simple: just add a var keyword in both for loops:

    function floodFill(col, row) {
        grid[col][row] = 1;
        for (var c_off = -1; c_off < 2; c_off++) {
            for (var r_off = -1; r_off < 2; r_off++) {
            var i = col + c_off;
            var j = row + r_off;
            if (i > -1 && i < cols && j > -1 && j < rows) {
                    if (grid[i][j] != 1) {
                        floodFill(i, j);
                    }
                }
            }
        }
    }

Appendix

You can move the detection of out-of-grid condition, and the check whether the given point is already filled, to the beginning of the function (instead of doing it just before the recursive call). Some may argue that the resulting code is simpler to understand:

    function floodFill(col, row) {
        if (col < 0 || col >= cols || row < 0 || row >= rows) {
            return;
        }

        if (grid[col][row] == 1) {
            return;
        }
        grid[col][row] = 1;
        for (var c_off = -1; c_off < 2; c_off++) {
            for (var r_off = -1; r_off < 2; r_off++) {
                floodFill(col + c_off, row + r_off);
            }
        }
    }

Upvotes: 1

Arnas Dičkus
Arnas Dičkus

Reputation: 677

I think Itay Maman answer is probably better. I solved it this way. by changing c_off < 5 and r_off < 5

var grid = [[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]];
var cols = grid.length;
var rows = grid[0].length;
floodFill(1, 1)

function floodFill(col, row) {

   grid[col][row] = 1;

  for (c_off = -1; c_off < 5; c_off++) {
    for (r_off = -1; r_off < 5; r_off++) {
      var i = col + c_off;
      var j = row + r_off;
      if (i > -1 && i < cols && j > -1 && j < rows) {
        if (grid[i][j] != 1) {
          floodFill(i, j);
        }
      }
    }
  }
}

console.log(grid);

Upvotes: 0

Related Questions