计算矩阵中的零岛 [英] count islands of zeros in a matrix

问题描述

我正在尝试按照著名的计数岛问题进行编程.

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

它没有给我预期的输出.我哪里错了?我的假设是如果 0 接触矩阵的第 0 行或列或维度 .. 它不会被视为岛

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

这是我的代码

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);
    }
}

推荐答案

以下解决方案经过测试，适用于任何可能性

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();
        }
    }

}

这篇关于计算矩阵中的零岛的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！