Counting Islands in a Binary Matrix

Given a 2D grid consisting of 1 (land) and 0 (water), count the number of islands. An island is formed by adjacent lands connectde horizontaly or vertically, surrounded by water. The grid boundaries are considered water.

Input Format:

• First line: two integers N, M (matrix dimensions)
• Next N lines: M space-separated integers (0 or 1)

Output: Single integer representing island count

Example:

4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

Output: 3

Constraints: 1 ≤ N, M ≤ 50

DFS Implementation

import java.util.*;

class IslandCounter {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int rows = input.nextInt();
        int cols = input.nextInt();
        int[][] grid = new int[rows][cols];
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                grid[i][j] = input.nextInt();
            }
        }
        
        int islandCount = 0;
        boolean[][] visited = new boolean[rows][cols];
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (!visited[i][j] && grid[i][j] == 1) {
                    islandCount++;
                    markIslandDFS(visited, grid, i, j);
                }
            }
        }
        System.out.println(islandCount);
    }
    
    static void markIslandDFS(boolean[][] visited, int[][] grid, int row, int col) {
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        
        for (int[] dir : directions) {
            int newRow = row + dir[0];
            int newCol = col + dir[1];
            
            if (newRow >= 0 && newRow < grid.length && 
                newCol >= 0 && newCol < grid[0].length &&
                !visited[newRow][newCol] && grid[newRow][newCol] == 1) {
                visited[newRow][newCol] = true;
                markIslandDFS(visited, grid, newRow, newCol);
            }
        }
    }
}

BFS Implementation

import java.util.*;

class IslandCounterBFS {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int rows = input.nextInt();
        int cols = input.nextInt();
        int[][] grid = new int[rows][cols];
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                grid[i][j] = input.nextInt();
            }
        }
        
        int islandCount = 0;
        boolean[][] visited = new boolean[rows][cols];
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (!visited[i][j] && grid[i][j] == 1) {
                    islandCount++;
                    markIslandBFS(visited, grid, i, j);
                }
            }
        }
        System.out.println(islandCount);
    }
    
    static void markIslandBFS(boolean[][] visited, int[][] grid, int startRow, int startCol) {
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{startRow, startCol});
        visited[startRow][startCol] = true;
        
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int row = current[0];
            int col = current[1];
            
            for (int[] dir : directions) {
                int newRow = row + dir[0];
                int newCol = col + dir[1];
                
                if (newRow >= 0 && newRow < grid.length && 
                    newCol >= 0 && newCol < grid[0].length &&
                    !visited[newRow][newCol] && grid[newRow][newCol] == 1) {
                    visited[newRow][newCol] = true;
                    queue.add(new int[]{newRow, newCol});
                }
            }
        }
    }
}

Finding Maximum Island Area

Given the same grid structure, find the maximum area of any island, where area is the number of connected land cells.

Input/Output Format: Same as island counting

Example: Same input produces output: 4

BFS Area Calculation

import java.util.*;

class MaxIslandArea {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int rows = input.nextInt();
        int cols = input.nextInt();
        int[][] grid = new int[rows][cols];
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                grid[i][j] = input.nextInt();
            }
        }
        
        int maxArea = 0;
        boolean[][] visited = new boolean[rows][cols];
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (!visited[i][j] && grid[i][j] == 1) {
                    int area = calculateAreaBFS(visited, grid, i, j);
                    maxArea = Math.max(maxArea, area);
                }
            }
        }
        System.out.println(maxArea);
    }
    
    static int calculateAreaBFS(boolean[][] visited, int[][] grid, int startRow, int startCol) {
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{startRow, startCol});
        visited[startRow][startCol] = true;
        int area = 1;
        
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int row = current[0];
            int col = current[1];
            
            for (int[] dir : directions) {
                int newRow = row + dir[0];
                int newCol = col + dir[1];
                
                if (newRow >= 0 && newRow < grid.length && 
                    newCol >= 0 && newCol < grid[0].length &&
                    !visited[newRow][newCol] && grid[newRow][newCol] == 1) {
                    visited[newRow][newCol] = true;
                    queue.add(new int[]{newRow, newCol});
                    area++;
                }
            }
        }
        return area;
    }
}