NumberIslands.java

import java.util.*;

public class NumberIslands {

    // Marking the Pair class as static so it can be used in static methods
    public static class Pair {
        int first, second;

        public Pair(int first, int second) {
            this.first = first;
            this.second = second;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("Enter the number of rows:");
        int n = scanner.nextInt();
        System.out.println("Enter the number of columns:");
        int m = scanner.nextInt();

        int[][] grid = new int[n][m];
        System.out.println("Enter the grid (use '1' for land and '0' for water):");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = scanner.nextInt();
            }
        }

        NumberIslands islands = new NumberIslands();
        int count = islands.numOfIslands(grid);
        System.out.println("Number of islands: " + count);
        scanner.close();
    }

    public void bfs(int ro, int co, int[][] vis, int[][] grid) {
        vis[ro][co] = 1;
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(ro, co));
        int n = grid.length;
        int m = grid[0].length;

        while (!q.isEmpty()) {
            int row = q.peek().first;
            int col = q.peek().second;
            q.remove();

            // Checking all 8 directions
            for (int i = -1; i <= 1; i++) {
                for (int j = -1; j <= 1; j++) {
                    int r = row + i;
                    int c = col + j;

                    if (r >= 0 && r < n && c >= 0 && c < m && grid[r][c] == 1 && vis[r][c] == 0) {
                        vis[r][c] = 1;
                        q.add(new Pair(r, c));
                    }
                }
            }
        }
    }

    public int numOfIslands(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int[][] vis = new int[n][m];
        int count = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (vis[i][j] == 0 && grid[i][j] == 1) {
                    count++;
                    bfs(i, j, vis, grid);
                }
            }
        }
        return count;
    }
}