200. Number of Islands Leetcode Solution

class Solution {
public:
    void dfs(vector>& grid, int row, int col) {
        // Base cases for recursion
        if (row < 0 || row >= grid.size() || col < 0 || col >= grid[0].size() || grid[row][col] != '1') {
            return;
        }
        
        // Mark the current cell as visited
        grid[row][col] = '2';
        
        // Recursive calls in 4 directions
        dfs(grid, row - 1, col); // Up
        dfs(grid, row + 1, col); // Down
        dfs(grid, row, col - 1); // Left
        dfs(grid, row, col + 1); // Right
    }
    
    int numIslands(vector>& grid) {
        int islandCount = 0;
        
        // Traverse each cell in the grid
        for (int row = 0; row < grid.size(); row++) {
            for (int col = 0; col < grid[0].size(); col++) {
                if (grid[row][col] == '1') {
                    islandCount++;
                    dfs(grid, row, col);
                }
            }
        }
        
        return islandCount;
    }
};

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


class Pair {
    int first;
    int second;

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

class Solution {
    // Helper function for BFS traversal
    private void bfs(int row, int col, int[][] visit, char[][] grid) {
        visit[row][col] = 1;
        Queue q = new LinkedList();
        q.add(new Pair(row, col));

        int n = grid.length;
        int m = grid[0].length;

        // Define movements: up, right, down, left
        int[] rowMovement = {-1, 0, 1, 0};
        int[] colMovement = {0, 1, 0, -1};

        // BFS traversal
        while (!q.isEmpty()) {
            int currentRow = q.peek().first;
            int currentCol = q.peek().second;
            q.remove();

            // Explore all four directions
            for (int direction = 0; direction < 4; direction++) {
                int newRow = currentRow + rowMovement[direction];
                int newCol = currentCol + colMovement[direction];

                // Check if the new position is valid and has '1'
                if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < m &&
                    grid[newRow][newCol] == '1' && visit[newRow][newCol] == 0) {
                    // Mark as visited and add to the queue for further exploration
                    visit[newRow][newCol] = 1;
                    q.add(new Pair(newRow, newCol));
                }
            }
        }
    }

    // Main function to count islands
    public int numIslands(char[][] grid) {
        int count = 0;
        int row = grid.length;
        int column = grid[0].length;
        int[][] visit = new int[row][column];

        // Iterate through each cell in the grid
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                // If the cell contains '1' and has not been visited, start BFS
                if (grid[i][j] == '1' && visit[i][j] == 0) {
                    count++;
                    bfs(i, j, visit, grid);
                }
            }
        }
        // Return the count of islands
        return count;
    }
}

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        output = 0 
        directions = [[0, 1], [0, -1], [1, 0], [-1, 0]] 
        visited = set() 

        def dfs(curr_x, curr_y):
            visited.add((curr_x, curr_y))
            for dir_x, dir_y in directions:
                next_x, next_y = curr_x + dir_x, curr_y + dir_y 
                if next_x in range(len(grid)) and next_y in range(len(grid[0])) and grid[next_x][next_y] == "1" and (next_x, next_y) not in visited:
                    dfs(next_x, next_y)

        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == "1" and (i, j) not in visited:
                    output += 1 
                    dfs(i, j)

        return output