Number of Closed Islands

class Solution {
public:
    int countClosedIslands(vector<vector<int>>& matrix) {
        int rows = matrix.size();
        int cols = matrix[0].size();
        int totalClosedIslands = 0;
        vector<vector<bool>> visited(rows, vector<bool>(cols, false));
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == 0 && !visited[i][j] && depthFirstSearch(i, j, rows, cols, matrix, visited)) {
                    totalClosedIslands++;
                }
            }
        }
        return totalClosedIslands;
    }
    
    bool depthFirstSearch(int x, int y, int rows, int cols, vector<vector<int>>& matrix, vector<vector<bool>>& visited) {
        if (x < 0 || x >= rows || y < 0 || y >= cols) {
            return false;
        }
        if (matrix[x][y] == 1 || visited[x][y]) {
            return true;
        }
    
        visited[x][y] = true;
        bool surrounded = true;
        vector<int> dx {0, 1, 0, -1};
        vector<int> dy {-1, 0, 1, 0};
    
        for (int direction = 0; direction < 4; direction++) {
            int newRow = x + dx[direction];
            int newCol = y + dy[direction];
            if (!depthFirstSearch(newRow, newCol, rows, cols, matrix, visited)) {
                surrounded = false;
            }
        }
    
        return surrounded;
    }
};

The solution involves a C++ class that calculates the number of "closed islands" in a given 2D grid. Each cell in the grid can either be land (0) or water (1). A "closed island" is a group of 0s completely surrounded by 1s, excluding the perimeter of the grid which must not be considered when detecting a closed island.

The primary function countClosedIslands iterates through each cell in the grid, utilizing a helper function depthFirstSearch (DFS) when encountering a cell that is land and has not yet been visited. The depthFirstSearch function checks the boundaries and paths recursively to determine if an island surrounded entirely by water is found, without touching the grid's edges. It uses additional data structures:

• visited tracks whether a cell has been processed.
• totalClosedIslands counts the number of closed islands detected.
• Arrays dx and dy define movement directions (left, down, right, up) for the DFS to explore surrounding cells.

When a connected group of 0s qualifies as a closed island which means during DFS traversal if it doesn't touch the boundary and surrounded by 1s, the count totalClosedIslands is incremented. The final count is returned after the grid has been fully traversed. This solution efficiently handles the discovery of closed islands using depth-first search, providing a robust way to navigate through the matrix with clear direction changes and boolean checks for conditions of being on an island or in water.

class Solution {
    public int countClosedIslands(int[][] terrain) {
        int height = terrain.length;
        int width = terrain[0].length;
        boolean[][] visited = new boolean[height][width];
        int closedIslandCount = 0;
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                if (terrain[i][j] == 0 && !visited[i][j] && depthFirstSearch(i, j, height, width, terrain, visited)) {
                    closedIslandCount++;
                }
            }
        }
        return closedIslandCount;
    }
    
    public boolean depthFirstSearch(int x, int y, int height, int width, int[][] terrain, boolean[][] visited) {
        if (x < 0 || x >= height || y < 0 || y >= width) {
            return false;
        }
        if (terrain[x][y] == 1 || visited[x][y]) {
            return true;
        }
    
        visited[x][y] = true;
        boolean isEnclosed = true;
        int[] deltaX = {0, 1, 0, -1};
        int[] deltaY = {-1, 0, 1, 0};
    
        for (int i = 0; i < 4; i++) {
            int nx = x + deltaX[i];
            int ny = y + deltaY[i];
            if (!depthFirstSearch(nx, ny, height, width, terrain, visited)) {
                isEnclosed = false;
            }
        }
    
        return isEnclosed;
    }
}

This Java solution focuses on finding the number of "closed islands" in a 2D grid, where "closed islands" are groups of adjacent cells with zero values completely surrounded by one-valued cells or the grid boundaries. Follow these steps to understand the code implementation:

1. Define the countClosedIslands method to count the number of closed islands in the grid. Create a boolean array visited to track cells that have been checked.
2. Iterate over each cell in the grid. If a cell has not been visited and its value is zero, conduct a Depth-First Search (DFS) starting from that cell.
3. Increment the closedIslandCount if the DFS deems the island as closed.
4. Implement the depthFirstSearch method to check if an island (connected zeroes) is closed. Use recursion to check all four adjacent cells (up, down, left, right).
5. Return false immediately if the search goes out of bounds, indicating the island is not closed since it touches an edge.
6. Mark the current cell as visited. If any recursive call to an adjacent cell returns false, the island is not closed.
7. Return true if all recursive calls confirm the surrounding cells are boundaries (either grid edges or one-valued cells).

By following these steps, the solution effectively checks and counts all closed islands in a given grid using DFS strategy, marking visited cells to prevent unnecessary rechecks and ensuring efficient traversal of the grid.

class IslandCounter:
    def countClosedIslands(self, islandGrid: List[List[int]]) -> int:
        height = len(islandGrid)
        width = len(islandGrid[0])
        visited = [[False] * width for _ in range(height)]
        islandCount = 0
    
        for row in range(height):
            for col in range(width):
                if islandGrid[row][col] == 0 and not visited[row][col] and self.runDFS(row, col, height, width, islandGrid, visited):
                    islandCount += 1
        return islandCount
    
    def runDFS(self, x: int, y: int, height: int, width: int, islandGrid: List[List[int]], visited: List[List[bool]]) -> bool:
        if x < 0 or x >= height or y < 0 or y >= width:
            return False
        if islandGrid[x][y] == 1 or visited[x][y]:
            return True
    
        visited[x][y] = True
        closed = True
        dx = [0, 1, 0, -1]
        dy = [-1, 0, 1, 0]
    
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if not self.runDFS(nx, ny, height, width, islandGrid, visited):
                closed = False
    
        return closed

The solution involves counting the number of "closed islands" in a given grid using Python. A closed island is defined as a group of zeros (0's) completely surrounded by ones (1's), excluding those that touch the boundaries of the grid.

To tackle this problem:

• Initialize a IslandCounter class with two methods: countClosedIslands and runDFS.
• countClosedIslands iterates through the grid and uses depth-first search (DFS) to explore potential islands marked by zeros.
• Implement runDFS to navigate through the grid, marking the visited cells and checking if the current island is closed. The method uses recursion to check all four possible directions (up, down, left, right) from the current position.
• Return True recursively in runDFS only if every explored path indicates the segment of zeros is surrounded by ones.
• Ensure edge cases are handled properly, such as grid edges not being part of a closed island.

Key steps in runDFS include:

• Check boundary conditions to terminate the DFS if it reaches outside the grid.
• Skip searching already visited cells or cells with ones.
• Mark the current cell as visited and continue the search in all four cardinal directions.
• Use a closed flag to determine whether emerging from a cell's DFS indicates it's still possibly a closed island.

By the end of processing, countClosedIslands returns the number of isolated, bordered zeros that form closed islands, ensuring an accurate count of such groups in the grid.