Leetcode 200. Number of Islands

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.

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

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] is '0' or '1'.

//C++

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int numIsland = 0;

        for(int i = 0; i < grid.size(); i++){
            for(int j = 0; j < grid[0].size(); j++){
                if(grid[i][j] == '1'){
                    numIsland += dfs(grid, i, j);
                }
            }
        }
        return numIsland;
    }
    
    int dfs(vector<vector<char>>& grid, int i, int j)
    {
        if(i < 0 || i >= grid.size() || j < 0 || j >= grid[i].size() || grid[i][j] == '0'){
            return 0;
        }
        grid[i][j] = '0';
        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j );
        dfs(grid, i, j + 1 );
        dfs(grid, i, j - 1 );

        return 1;
    }
};
//Java
public class NumIsland {

    public static void main(String[] args) {
        char[][] grid = { { '1', '1', '1', '1', '0' }, { '1', '1', '0', '1', '0' }, { '1', '1', '0', '0', '0' },
                { '0', '0', '0', '0', '0' } };
        System.out.println(new Solution().numIslands(grid));

    }
}

class Solution {
    public int numIslands(char[][] grid) {
        // if (grid == null || grid.length == 0) {
        // return 0;
        // }

        int numIsland = 0;

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    numIsland++;
                }
            }
        }
        return numIsland;
    }

    public void dfs(char[][] grid, int i, int j) {
        if (i < 0 || i > grid.length - 1 || j < 0 || j > grid[i].length - 1 || grid[i][j] == '0') {
            return;
        }
        grid[i][j] = '0';
        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i, j - 1);

        // dfs(grid, i + 1, j + 1);
        // dfs(grid, i + 1, j - 1);
        // dfs(grid, i - 1, j + 1);
        // dfs(grid, i - 1, j - 1);
    }
}
//Javascript
var numIslands = function(grid) {
    // if (grid == null || grid.length == 0) {
    //     return 0;
    // }

    let numIsland = 0;

    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == '1') {
                dfs(grid, i, j);
                numIsland++;
            }
        }
    }
    return numIsland;
};

var dfs = function(grid, i, j) {
    if (i < 0 || i >= grid.length || j < 0 || j >= grid[i].length || grid[i][j] == '0') {
        return;
    }
    grid[i][j] = '0';
    dfs(grid, i + 1, j);
    dfs(grid, i - 1, j);
    dfs(grid, i, j + 1);
    dfs(grid, i, j - 1);

    // dfs(grid, i + 1, j + 1);
    // dfs(grid, i + 1, j - 1);
    // dfs(grid, i - 1, j + 1);
    // dfs(grid, i - 1, j - 1);
}

let grid = [[ '1', '1', '1', '1', '0' ], [ '1', '1', '0', '1', '0' ], [ '1', '1', '0', '0', '0' ],
[ '0', '0', '0', '0', '0' ]];

console.log(numIslands(grid));
//C#
public class Solution {
    public int NumIslands(char[][] grid) {
        // if(grid == null || grid.Length == 0)
        // {
            // return 0;
        // }
        int numIsland = 0;

        for(int i = 0; i < grid.Length; i++){
            for(int j = 0; j < grid[0].Length; j++){
                if(grid[i][j] == '1'){
                    numIsland += dfs(grid, i, j);
                }
            }
        }
        return numIsland;
    }
    
    int dfs(char[][] grid, int i, int j)
    {
        if(i < 0 || i >= grid.Length || j < 0 || j >= grid[i].Length || grid[i][j] == '0'){
            return 0;
        }
        grid[i][j] = '0';
        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j );
        dfs(grid, i, j + 1 );
        dfs(grid, i, j - 1 );

        // dfs(grid, i + 1, j + 1);
        // dfs(grid, i + 1, j - 1);
        // dfs(grid, i - 1, j + 1);
        // dfs(grid, i - 1, j - 1);
        
        return 1;
    }
}