【解決方法】カウント アイランドの Javascript 再帰解決策

プログラミングQA


島の数の問題に対するこの再帰的な解決策を理解しようとしています。

console.log(grid) 以来、4回目の再帰呼び出しの後に追跡できなくなりました
次の 1 が 0 に変わるのは、行 3、列 0 であることを示しています。
しかし、私の心は、行0列1であるべきだったと言います。

continue ステートメントが反復を中断し、次のステートメントに進むことはわかっています。

grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","1"]
]


function numIslands(grid) {
    const H = grid.length;  // 4
    const W = grid[0].length; // 5

    let count = 0;
    
    for (let r = 0; r < H; r++) { // Row
      for (let c = 0; c < W; c++) { // Col
        if (grid[r][c] === '0') continue;
        
        count++; // 3
        dfs(r, c);
      }
    }
    return count;
    
    function dfs(r, c) { // Gets called first time with (0, 0)

      if (r < 0 || c < 0 || r === H || c === W) return; // Checks if out of bounds.
      if (grid[r][c] === '0') return; 
      console.log("Row: ",  r, "Col: ", c)
      
      grid[r][c] = '0'; // (0, 0) turns from  1 to 0.
      dfs(r-1, c); // (-1, 0) returns due to out of bounds
      dfs(r+1, c); // (1, 0) turns from 1 to 0.
      dfs(r, c-1); // (0, -1) retuns due to out of bounds
      dfs(r, c+1); // 
    }
  }

  console.log(numIslands(grid))

私が試したこと:

これを数時間テスト/分解します+。
この正確な問題に対する他の再帰的な解決策とそれらの理解。

コメント

タイトルとURLをコピーしました