矩阵中 1 的 Groups/Islands 个数：定义说明

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 水平或垂直相邻。

Answer 2

countgroup=1
countgroup_of_one_array=[]
def check_to_search(p_i,p_j,matrix):
    allow=True
    if p_j <0:
        allow=False
    if p_j >len(matrix[0])-1:
        allow=False
    if p_i<0:
        allow=False
    if p_i>len(matrix)-1:
        allow=False
    return allow



def looking_for1(p_i,p_j,matrix,countgroup):
    # global countgroup
    if matrix[p_i][p_j]==1:
        matrix[p_i][p_j]=0
        if check_to_search(p_i,p_j+1,matrix):
            if matrix[p_i][p_j+1] == 1:
                countgroup =countgroup+1
                countgroup = looking_for1(p_i,p_j+1,matrix,countgroup)
        if check_to_search(p_i,p_j-1,matrix):
            if matrix[p_i][p_j-1] == 1:
                countgroup =countgroup+1
                countgroup = looking_for1(p_i,p_j-1,matrix,countgroup)
        if check_to_search(p_i+1,p_j,matrix):
            if matrix[p_i+1][p_j] == 1:
                countgroup =countgroup+1
                countgroup = looking_for1(p_i+1,p_j,matrix,countgroup)
        if check_to_search(p_i-1,p_j,matrix):
            if matrix[p_i-1][p_j] == 1:
                countgroup =countgroup+1
                countgroup = looking_for1(p_i-1,p_j,matrix,countgroup)

    return countgroup


myarray=[[0,0,1,0,1],
         [1,1,0,1,0],
         [1,1,0,1,0],
         [0,0,0,0,0],
         [1,1,0,1,0]]

for i in range (0, len(myarray)):
    for j in range (0, len(myarray[i])):
        a= looking_for1(i,j,myarray,countgroup)
        if a >=2 :

            countgroup_of_one_array.append(a)

print("number of group of 1 is  : "+format(len(countgroup_of_one_array)) )
print((countgroup_of_one_array))

答案： 3个 [4,2,2]

矩阵中 1 的 Groups/Islands 个数：定义说明

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

java

algorithm

flood-fill

gaps-and-islands