count islands of zeros in a matrix

Question

I am trying to program following well-known counting islands problem.

and it is not giving me the expected output. Where am I going wrong? My assumption is if 0's touch 0th row or column or dimension of matrix .. it will not be treated as island

Here is my code

public class Matrix {
    static int rowCount = 5;
    static int columnCount = 4;
    static int[][] matrix = {   {1,1,1,1,1},
                                {1,0,0,0,1},
                                {1,1,1,1,1},
                                {1,1,1,0,1}
                     };
    static boolean[][] visited = new boolean[rowCount][columnCount];    
    private static int countIslands = 0;    
    public static void main(String[] args) {
        try{
            for(int i=0; i<rowCount; i++){
                for(int j=0; j<columnCount; j++){
                    if(matrix[i][j]==0){                        
                        checkZeros(matrix, i, j);
                        System.out.println("returned " + i + j);
                    }
                }
            }
            System.out.println(visited);
        }catch(Exception e){
        }
        System.out.println(countIslands);
    }
    private static void checkZeros(int[][] matrix2, int i, int j) {
        boolean valueWithinLimits = withinLimits(i,j);      
        System.out.println("checking for " + i + j);
        if(valueWithinLimits) && checkAlreadyVisited(i,j)){
            if(matrix[i][j+1]==0){ 
                checkZeros(matrix2, i, j+1);   
            }
            if(matrix[i+1][j+1]==0){ 
                checkZeros(matrix2, i+1, j+1);
            }
            if(matrix[i+1][j]==0){
                checkZeros(matrix2, i+1, j);   
            } 
            if(matrix[i+1][j-1]==0){
                checkZeros(matrix2, i-1, j-1);   
            }           
            visited[i][j] = true;
            System.out.println("i reached here when ij are : " + i + j);
            countIslands ++;
        }
    }
    private static boolean checkAlreadyVisited(int i, int j) {
        System.out.println("visited found for " + i + j);
        return visited[i][j-1] || visited[i-1][j-1] || visited[i-1][j] || visited[i-1][j+1];
    }
    private static boolean withinLimits(int i, int j) {
        return (i>0 && i<rowCount-1 && j>0 && j<columnCount-1);
    }
}

Answer 1

The below solution is tested and works perfectly fine for any possibility

package com.divyanshu.island;

/**
 * <b>Assumption 1 : 1 is Land, 0 is water.</b>
 * <b>Assumption 2 : It is all water outside the matrix.</b>
 * 
 * Instantiate IslandCounter by passing a m*n matrix.
 * Method getIslandCount gives you the count of island formed.
 * 
 * </br></br>Or</br></br>
 * 
 * Method getIslandCount gives the count of all connected 1s in a m*n matrix with values in 1 or 0.
 */
public class IslandCounter {

    private Integer[][] matrix;

    public IslandCounter(Integer[][] matrix) {
        this.matrix = matrix;
    }

    public int getIslandCount() {
        int count = 0;
        if (matrix == null || matrix.length == 0) {
            return count;
        }
        Integer[][] tempMatrix = matrix.clone();
        for (int i = 0; i < tempMatrix.length; i++) {
            for (int j = 0; j < tempMatrix[i].length; j++) {
                if (detectIsland(tempMatrix, false, i, j, matrix.length - 1, matrix[i].length - 1)) {
                    count++;
                }
            }
        }
        return count;
    }

    private boolean detectIsland(Integer[][] tempMatrix,
                                 boolean islandDetected,
                                 int i,
                                 int j,
                                 int iMax,
                                 int jMax) {
        if (i > iMax || j > jMax || i < 0 || j < 0 || tempMatrix[i][j] == 0) {
            return islandDetected;
        } else {
            tempMatrix[i][j] = 0;
            islandDetected = true;
            detectIsland(tempMatrix, islandDetected, i - 1, j, iMax, jMax);
            detectIsland(tempMatrix, islandDetected, i, j - 1, iMax, jMax);
            detectIsland(tempMatrix, islandDetected, i + 1, j, iMax, jMax);
            detectIsland(tempMatrix, islandDetected, i, j + 1, iMax, jMax);
        }
        return islandDetected;
    }

}


===================================================================================

/**
 * 
 */
package com.divyanshu.island;

import java.util.Random;

/**
 *This is a Main-Class to test the IslandCounter.
 */
public class IslandTest {

    /**
     * @param args
     */
    public static void main(String[] args) {
        Integer[][] matrix = generateMatrix();
        printMatrix(matrix);
        IslandCounter counter = new IslandCounter(matrix);
        System.out.println("Total islands in the matrix : " + counter.getIslandCount());

    }

    private static Integer[][] generateMatrix() {
        Integer[][] matrix = new Integer[4][4];
        Random random = new Random();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                matrix[i][j] = random.nextInt(2);
            }
        }
        return matrix;
    }

    private static void printMatrix(Integer[][] matrix) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }
    }

}

Answer 2

I think there are multiple problems in your code.

Your visited matrix is full of false, which mean that checkAlreadyVisited will always return false. Also, I don't understand why does this method checks surroundings to see if the current location is visited. Using a temporary matrix like visited is a good idea, but you should print both map to ensure that it works.

countIslands is never incremented because of the previous error, but once you'll have resolved it, it will be incremented on every call (which should match the number of 0 on your map). If you want his solution to work with the border constraint, you must apply his detectIsland on each border before the for loop.

Divyanshu's solution works, except that it counts 1 and doesn't consider that an island touching a border is not an island (as you said).

To correct your solution, the visited matrix must be a copy of the matrix before using it, checkAlreadyVisited should only scan [i][j] and not its surrondings, and you shouldn't increment countIslands at each call.

Again, print your maps at each turns and use an easier matric like:

static int[][] matrix = {{1,1,1},
                         {1,0,1},
                         {1,1,1},};

(Didn't saw this question was three monsth old... anyway, here you go)

Answer 3

What you can do to improve is to add an exclusion array: an array of elements that are zeros. For example, if you find a zero within limits, you can start looking around and see if there are any zeros. Keep looking until you find all of them. Then add every single one of these zeros to the exclusion array, and when you continue with the loop, make sure it skips the elements in the exclusion array. This is not code, but the outline of the logic of the program.