Count number of islands in a 2d matrix with variation

Question

"Given a boolean 2D matrix, find the number of islands. A group of connected 1s forms an island."

In this variation of the counting number of islands question, we are meant to count the number of islands COMPLETELY surrounded by water. That is, no 1s at the edge should be counted, and no island at the edge should be counted either. We only want the 1s surrounded by only 0s at all sides.

I tried using the popular dfs technique with some modifications. I don't traverse the edges of the matrix all. This obviously only satisfies a few cases. It fails for the following example as it returns 2 instead of 1:

I have also tried reducing the count everytime I backtrack, but this is obviously a futile effort because the count ends up being less than zero. Lastly I tried reducing the count while placing a lower bound at 0. This just returns 0 all the time. I am definitely missing something. Any help?

Here's the code below:

class Islands { 
    // No of rows and columns 
    static final int ROW = 5, COL = 5; 
    int gcount;

    // A function to check if a given cell (row, col) can 
    // be included in DFS 
    boolean isSafe(int M[][], int row, int col, 
                   boolean visited[][]) 
    { 
        // row number is in range, column number is in range 
        // and value is 1 and not yet visited 
        return (row >= 1) && (row < ROW-1) && (col >= 1) && // used to be row >= 0 && row < ROW && col >=0
                (col < COL-1) && (M[row][col] == 1 && !visited[row][col]); //col < COL
    } 

    // A utility function to do DFS for a 2D boolean matrix. 
    // It only considers the 8 neighbors as adjacent vertices 
    void DFS(int M[][], int row, int col, boolean visited[][]) 
    { 
        // These arrays are used to get row and column numbers 
        // of 8 neighbors of a given cell 
        int rowNbr[] = new int[] { -1, -1, -1, 0, 0, 1, 1, 1 }; 
        int colNbr[] = new int[] { -1, 0, 1, -1, 1, -1, 0, 1 }; 

        // Mark this cell as visited 
        visited[row][col] = true; 

        // Recur for all connected neighbors 
        for (int k = 0; k < 8; ++k) 
            if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited)) {
                System.out.println("here");
                ++gcount;
                DFS(M, row + rowNbr[k], col + colNbr[k], visited);
            }
            /*else {
                gcount--;
                if(gcount < 1) {
                    gcount = 0;
                }
            }*/
    } 

    // The main function that returns count of islands in a given 
    // boolean 2D matrix 
    int countIslands(int M[][]) 
    { 
        // Make a bool array to mark visited cells. 
        // Initially all cells are unvisited 
        boolean visited[][] = new boolean[ROW][COL]; 

        // Initialize count as 0 and traverse through the all cells 
        // of given matrix 
        int count = 0; 
        for (int i = 1; i < ROW-1; ++i) //I changed this from ROW
            for (int j = 1; j < COL-1; ++j) //I changed this from COL
                if (M[i][j] == 1 && !visited[i][j]) // If a cell with 
                { // value 1 is not 
                    // visited yet, then new island found, Visit all 
                    // cells in this island and increment island count 
                    DFS(M, i, j, visited); 
                    //++gcount; 
                } 

        return gcount; 
    } 

Answer 1

In countIslands first visit all edge cells (top and bottom rows, left and right columns). This will mark all islands reachable from an edge cell as visited.

for (int j = 0; j < COL; ++j)
{
    if (M[0][j] == 1 && !visited[0][j])
        DFS(M, 0, j, visited);
    if (M[ROW - 1][j] == 1 && !visited[ROW - 1][j])
        DFS(M, ROW - 1, j, visited);
}

for (int i = 1; i < ROW - 1; ++i) // I changed this from ROW
{
    if (M[i][0] == 1 && !visited[i][0])
        DFS(M, i, 0, visited);
    if (M[i][COL - 1] == 1 && !visited[i][COL - 1])
        DFS(M, i, COL - 1, visited);
}

Then you visit the inner cells as you do currently.

int count = 0;
for (int i = 1; i < ROW - 1; ++i)
{
    for (int j = 1; j < COL - 1; ++j)
    {
        if (M[i][j] == 1 && !visited[i][j])
        {
            DFS(M, i, j, visited);
            count++;
        }
    }
}

Note that you have to increment the count here, not in DFS, since DFS is called for edge islands too.

One final note - these arrays should be declared at the class level, i.e. static, not in the DFS method. It's unnecessary to create them on each recursive call.

    int rowNbr[] = new int[] { -1, -1, -1, 0, 0, 1, 1, 1 }; 
    int colNbr[] = new int[] { -1, 0, 1, -1, 1, -1, 0, 1 };