J'y ai travaillé toute la journée et je n'arrive pas à comprendre pourquoi cet algorithme ne couvre pas toute la grille en commençant à la position grid[1][1].

Je commence par configurer la grille et calculer le nombre de lignes et de colonnes dans la grille pour me donner une limite sur les bords du tableau.

J'appelle ensuite la fonction, en définissant la position grid[1][1] = 1, en calculant le décalage et en m'assurant qu'il n'est pas en dehors du tableau et en m'assurant que la nouvelle position n'a pas déjà été appelée avant d'appeler la fonction de manière récursive.

Je n'arrive pas à comprendre pourquoi cela ne fonctionne pas !

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 ] ] 
*/
0
Charlie Brinley Codd 17 mars 2019 à 21:52

2 réponses

Meilleure réponse

C'est parce que c_off et r_off ne sont pas définis comme des variables locales (via les mots clés var ou let) donc ils sont traités comme des variables globales, ce qui signifie qu'une invocation récursive de floodFill() écrase les valeurs de son appel d'appel, interférant ainsi avec l'ordre d'itération de l'appelant.

La solution est simple : ajoutez simplement un mot-clé var dans les deux boucles 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);
                    }
                }
            }
        }
    }

Annexe

Vous pouvez déplacer la détection de la condition hors réseau et la vérification si le point donné est déjà rempli au début de la fonction (au lieu de le faire juste avant l'appel récursif). Certains peuvent soutenir que le code résultant est plus simple à comprendre :

    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);
            }
        }
    }
1
Itay Maman 18 mars 2019 à 10:21

Je pense que la réponse d'Itay Maman est probablement meilleure. Je l'ai résolu de cette façon. en changeant c_off < 5 et 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);
0
Arnas Dičkus 17 mars 2019 à 19:11