Number of Groups/Islands of 1's in a Matrix: D

问题:

I am studying various solutions for Number of Groups (or "islands") of 1's in a Matrix, and while the following clear & concise Java solution looks in the right direction, it also looks incomplete to me:

/*
 * Given a matrix of 0's and 1's, 
 * find the number of groups of 1's in the matrix.
 * 
 * A group of 1's is defined as all ADJACENT 1's 
 * vertically or horizontally but not diagonally.
*/

public class Islands {

    /**
     * main entry point
     */
    public static void main(String[] args) {
        int[][] A = new int[4][4];

        int totalNumGroups = 0; 
        int curCnt = 0;

        /*
         * Initialize 2-dimensional array with 1's and 0's (randomly!)
         * For testing/verification purpose only 
         */
        for(int x=0; x<A.length; x++) {
            for(int y=0; y<A[x].length; y++) {
                A[x][y] = (int) Math.round(Math.random());
                System.out.print(A[x][y] + " ");
            }
            System.out.println(" ");
        }

        /*
         * The crux of the solution: iterate through all (x,y):
         * If encountered a 1, 
         *  reset current count and 
         *  increase total number of groups by what clean_block returns.
         */
        for(int x=0; x<A.length; x++) {
            for(int y=0; y<A[x].length; y++) {
                if (A[x][y] == 1) {
                    curCnt = 0;  
                    totalNumGroups = totalNumGroups + cleanBlock(A, x,y, curCnt);    
                }
                // else (0), keep curCnt and totalNumGroups as are.
            }
        }

        System.out.println("\nTotal # of groups: " + totalNumGroups);
    }

    /*
     * Recursively clean found 1 and its adjacent 1's.
     */
    public static int cleanBlock(int[][] A, int x, int y, int cnt) { 
        A[x][y] = 0;
        if (inMatrix(x-1,y  ,A.length,A[0].length) == 1 && A[x-1][y] == 1) {
            cleanBlock(A, x-1,y  ,cnt); 
            cnt = 1;
            }
        if (inMatrix(x+1,y  ,A.length,A[0].length) == 1 && A[x+1][y] == 1) {
            cleanBlock(A, x+1,y  ,cnt); 
            cnt = 1;
            }
        if (inMatrix(x,y-1 ,A.length,A[0].length) == 1 && A[x][y-1] == 1) {
            cleanBlock(A, x,y-1  ,cnt); 
            cnt = 1;
            }
        if (inMatrix(x,y+1 ,A.length,A[0].length) == 1 && A[x][y+1] == 1) {
            cleanBlock(A, x,y+1  ,cnt); 
            cnt = 1;
            }

        return cnt;
    }

    public static int inMatrix(int x, int y, int lenX, int lenY) {
        if ( (x >= 0 && x <= (lenX-1)) && (y >= 0 && y <= (lenY-1)) )
            return 1;
        else
            return 0;
    }    
}

That is because it does not count a single 1 (surrounded by 0's) as a group. e.g. the output for this 4x4 matrix yields a single group only:

1 1 0 1  
1 0 0 0  
1 1 0 1  
1 0 0 0  

Total # of groups: 1

So, my question is: Is a single 1 surrounded by 0's considered a group?

回答1:

It's correct because according to the problem:

A group of 1's can be formed if a 1 is present either vertically or horizontally to the adjacent 1

So in your case, a lonely 1 can't be counted as a group because there's no other 1 adjacent horizontally or vertically.