Number of Islands

Given an m x n 2d grid 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

Approach

Java

public class NumberOfIslands {
    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(numIslands(grid));
    }

    static int numIslands(char[][] grid) {
        int n = grid.length;
        if (n == 0)
            return 0;
        int num_islands = 0;
        int m = grid[0].length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j, n, m);
                    num_islands += 1;
                }
            }
        }
        return num_islands;
    }

    static void dfs(char[][] gridint iint jint nint m) {

        // check if cell is valid or not
        if (i < 0 || j < 0 || i >= n || j >= m || grid[i][j] == '0')
            return;
        grid[i][j] = '0';

        // call for all four directions
        dfs(grid, i + 1, j, n, m);
        dfs(grid, i - 1, j, n, m);
        dfs(grid, i, j + 1, n, m);
        dfs(grid, i, j - 1, n, m);
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

void dfs(vector<vector<char>> &gridint iint jint nint m)
{

    //check if cell is valid or not
    if (i < 0 || j < 0 || i >= n || j >= m || grid[i][j] == '0')
        return;
    grid[i][j] = '0';

    //call for all four directions
    dfs(gridi + 1jnm);
    dfs(gridi - 1jnm);
    dfs(gridij + 1nm);
    dfs(gridij - 1nm);
}
int numIslands(vector<vector<char>> &grid)
{
    int n = grid.size();
    if (n == 0)
        return 0;
    int num_islands = 0;
    int m = grid[0].size();
    for (int i = 0i < ni++)
    {
        for (int j = 0j < mj++)
        {
            if (grid[i][j] == '1')
            {
                dfs(gridijnm);
                num_islands += 1;
            }
        }
    }
    return num_islands;
}

int main()
{
    vector<vector<char>> grid = {{'1''1''1''1''0'},
                                 {'1''1''0''1''0'},
                                 {'1''1''0''0''0'},
                                 {'0''0''0''0''0'}};
    cout << numIslands(grid);
    return 0;
}


No comments:

Post a Comment