Алгоритм Flood-fill в Javascript не заполняет всю сетку при использовании для циклов - PullRequest
0 голосов
/ 17 марта 2019

Я работал над этим весь день, и я не могу понять, почему этот алгоритм не охватывает всю сетку при запуске с координатной сетки [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 ] ] 
*/

Ответы [ 2 ]

1 голос
/ 17 марта 2019

Это потому, что c_off и r_off не определены как локальные переменные (через ключевые слова var или let), поэтому они обрабатываются как глобальные переменные, что означает, что рекурсивный вызов floodFill() перезаписываетзначения для его вызова вызова, таким образом вмешиваясь в порядок итераций вызывающего.

Исправление простое: просто добавьте ключевое слово var в оба цикла for:

    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);
            }
        }
    }
0 голосов
/ 17 марта 2019

Я думаю, что ответ Итая Мамана, вероятно, лучше. Я решил это таким образом. изменив 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);
...