javascript - 使用 for 循环时，Javascript 中的洪水填充算法不会填充整个网格

Question

我一整天都在研究这个问题，但我不明白为什么这个算法从位置 grid[1][1] 开始时没有覆盖整个网格。

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

然后我调用该函数，设置位置 grid[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);
            }
        }
    }