Count the islands — ( Java, C# …)

Given a boolean matrix,find the number of islands.

What is an island?

A group of connected 1s forms an island. For example, the below matrix contains 5 islands

{1, 1, 0, 0, 0},
{0, 1, 0, 0, 1},
{1, 0, 0, 1, 1},
{0, 0, 0, 0, 0},
{1, 0, 1, 0, 1}

Input Format

Number of rows ,number of columns in the first line.

Followed by the matrix.

Output Format

Print the number of islands.

Sample Input

5 5 
1 1 0 0 0
0 1 0 0 1
1 0 0 1 1
0 0 0 0 0
1 0 1 0 1

Sample Output

5

//C#using System;
using System.Collections.Generic;
using System.IO;
class IslandMatrix {

static int numIsland(int[][] 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;
}

static int dfs(int[][] 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;
}

static void Main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution */
int[] arrayMatrix = Array.ConvertAll(Console.ReadLine().Split(' '), arrTemp => Convert.ToInt32(arrTemp));

int n = arrayMatrix[0];
int m = arrayMatrix[1];
int[][] arr = new int[n][];

for (int i = 0; i < n; i++) {
arr[i] = Array.ConvertAll(Console.ReadLine().Split(' '), arrTemp => Convert.ToInt32(arrTemp));
}

System.Console.WriteLine(numIsland(arr));
}
}
//Java
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class IslandMatrix {
private static final Scanner scanner = new Scanner(System.in);

public static int numIsland(int[][] 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;
}

public static int dfs(int[][] 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;
}

public static void main(String[] args) {

String[] arrayLen = scanner.nextLine().split(" ");

int n = Integer.parseInt(arrayLen[0]);
int m = Integer.parseInt(arrayLen[1]);

int[][] arr = new int[n][m];

for (int i = 0; i < arr.length; i++) {
String[] arrRowItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

for (int j = 0; j < arr[i].length; j++) {
int arrItem = Integer.parseInt(arrRowItems[j]);
arr[i][j] = arrItem;
}
}

System.out.println(numIsland(arr));
scanner.close();
}
}