LeetCode Js-200. Number of Islands

    LeetCode Js-DFS/BFS

    Given an m x n 2D binary grid grid which represents a map of ‘1’s (land) and ‘0’s (water), return the number of islands.
    An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

    給予一個 m x n 的二維網格叫做 grid,這個網格中 "1" 代表陸地和 "0"代表水,回傳島嶼的數量。
    這個島嶼四面環水,相鄰陸地水平或垂直連結而成。
    您可以假設網格的所有四個邊緣皆被水包圍。
    

    Example 1:

    Input: grid = [
      ["1","1","1","1","0"],
      ["1","1","0","1","0"],
      ["1","1","0","0","0"],
      ["0","0","0","0","0"]
    ]
    Output: 1
    

    Example 2:

    Input: grid = [
      ["1","1","0","0","0"],
      ["1","1","0","0","0"],
      ["0","0","1","0","0"],
      ["0","0","0","1","1"]
    ]
    Output: 3
    

    solution:
    先建立 numIslands 計算島嶼的 funciton,遍歷這個二維網陣列,
    當碰到陸地的時候,就會依序將該土地的上下左右呼叫遞回函式 dfs 做深度搜尋,同時紀錄過的土地轉為 “0”。
    如完成(無任何延續土地)則紀錄 result++,最後回傳 result 的數量。

    Code 1: BigO(m x n)

    var numIslands = function(grid) {
      let result = 0
    
      //double for loop
      for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[i].length; j++) {
          //Check the grid position = 1
          if (grid[i][j] === "1") {
            dfs(grid, i , j)
            result++
          }
        }
      } 
      return result;
    };
    
    const dfs = (grid, i, j) => {
      //Not in the grid range
      if (i < 0 || j < 0 || i >= grid.length || j >= grid[i].length || grid[i][j] === "0" ) return;
    
      grid[i][j] = "0"
    
      dfs(grid, i, j - 1) //left
      dfs(grid, i, j + 1) //right
      dfs(grid, i - 1, j) //top
      dfs(grid, i + 1, j) //bottom
    }
    

    FlowChart:
    Example 1

    Input: grid = [
      ["1","1","1","1","0"],
      ["1","1","0","1","0"],
      ["1","1","0","0","0"],
      ["0","0","0","0","0"]
    ]
    
    grid[0][0]
    result++
    
    return result; //1
    

    Example 2

    Input: grid = [
      ["1","1","0","0","0"],
      ["1","1","0","0","0"],
      ["0","0","1","0","0"],
      ["0","0","0","1","1"]
    ]
    
    grid[0][0]
    result++
    
    grid[ 2, 2 ]
    result++
    
    grid[ 3, 3 ]
    result++
    
    return result; //3