Javascript 中的洪水填充算法在使用 for 循环时未填充整个网格

Question

我已经为此工作了一整天，我无法弄清楚为什么这个算法从位置 grid[1][1] 开始时没有覆盖整个网格。

我首先设置网格并计算网格中的行数和列数，以限制数组的边缘。

然后我调用函数，设置位置网格[1][1] = 1，计算偏移量并确保它不在数组之外，并确保在调用函数之前尚未调用新位置递归地。

我就是不明白为什么这不起作用！

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 ] ] 
*/

Answer 1

那是因为 c_off 和 r_off 没有定义为局部变量（通过 var 或 let 关键字）所以它们被视为全局变量，这意味着floodFill() 的递归调用会覆盖其调用调用的值，从而干扰调用者的迭代顺序。

修复很简单：只需在两个 for 循环中添加一个 var 关键字：

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

附录

您可以将检测超出网格条件和检查给定点是否已填充，移到函数的开头（而不是在递归调用之前进行）。有些人可能会争辩说生成的代码更容易理解：

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

Answer 2

我觉得 Itay Maman 的回答可能更好。我是这样解决的。通过更改 c_off < 5 和 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);

Javascript 中的洪水填充算法在使用 for 循环时未填充整个网格

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

javascript

arrays

recursion

function

flood-fill