java - 矩阵中 1 的组数/岛数 : Definition clarification

Question

我正在研究 Number of Groups (or "islands") of 1's in a Matrix 的各种解决方案，虽然以下清晰简洁的 Java 解决方案看起来方向正确，但对我来说它也不完整:

/*
 * 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;
    }    
}

那是因为它不将单个 1(被 0 包围)计为一个组。例如这个 4x4 矩阵的输出只产生一个组:

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

Total # of groups: 1

那么，我的问题是:被 0 包围的单个 1 是否被视为一个组？

Answer 1

这是正确的，因为根据问题:

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

所以在你的情况下，一个孤独的 1 不能算作一个组，因为没有其他 1 水平或垂直相邻。