Java 中的连通分量标记

Question

我正在尝试实现一种方法来查找给定大小的组数。输入是一个 n×n 二维数组，其中每个单元格的值为 0 或 1。如果单元格水平或垂直相邻（不是对角线）并且都具有值为 1。
组大小是该组中的单元格数。除了二维数组之外，还传递了一个整数数组 "t"。对于每个整数 t[i]，函数应确定大小等于该值的组数。该信息在整数数组 "answer" 中返回。
我试图解决这个问题，但未能通过所有提供的测试用例，我看不到输入或输出。我尝试了许多自定义测试用例，但没有发现任何问题。是否存在我的函数无法正常运行的场景？

static int[] countGroups(int[][] m, int[] t) {

    int[] answer;
    answer = new int[t.length];
    Arrays.fill(answer, 0);
    int[] sizes;
    int length = m.length;
    sizes = new int[(length * length)];
    Arrays.fill(sizes, 0);
    int[] subList;
    subList = new int[length * length];
    Arrays.fill(subList, 0);
    int groupID = 2;

    for(int j = 0; j < length; j++){
        for(int k = 0; k < length; k++){
            if(m[j][k] > 0){
                if((j != 0) && (k != 0)){
                    if((m[j-1][k] > 0) && (m[j][k-1] > 0)){
                        if(m[j-1][k] != m[j][k-1]){
                            if(m[j-1][k] < m[j][k-1]){
                                subList[(subList[(m[j][k-1])])] = m[j-1][k];
                                subList[(m[j][k-1])] = m[j-1][k];
                                m[j][k] = m[j-1][k];
                            }
                            else{
                                subList[(subList[(m[j-1][k])])] = m[j][k-1];
                                subList[(m[j-1][k])] = m[j][k-1];
                                m[j][k] = m[j][k-1];
                            }
                        }
                        else{
                            m[j][k] = m[j-1][k];
                        }
                    }
                    else if(m[j][k-1] > 0){
                        m[j][k] = m[j][k-1];
                    }
                    else if(m[j-1][k] > 0){
                        m[j][k] = m[j-1][k];
                    }
                    else{
                        groupID++;
                        m[j][k] = groupID;
                    }
                }
                else if((j == 0) && (k == 0)){
                    m[j][k] = groupID;
                }
                else if(k != 0){
                    if(m[j][k-1] > 0){
                        m[j][k] = m[j][k - 1];
                    }
                    else{
                        groupID++;
                        m[j][k] = groupID;
                    }
                }
                else if(k == 0){
                    if(m[j-1][k] > 0){
                        m[j][k] = m[j-1][k];
                    }
                    else{
                        groupID++;
                        m[j][k] = groupID;
                    }

                }
            }
            else{
            }
        }
    }
    for(int j = 0; j < length; j++){
        for(int k = 0; k < length; k++){
            if(m[j][k] > 0){
                if(subList[(m[j][k])] > 0){
                    m[j][k] = subList[(m[j][k])];
                }
            }
        }
    }
    for(int j = 0; j < length; j++){
        for(int k = 0; k < length; k++){
            if(m[j][k] > 0){
                sizes[(m[j][k])]++;
            }
        }
    }
    for(int x = 0; x < t.length; x++){
        for(int n = 0; n < sizes.length; n++){
            if(sizes[n] == t[x]){
                answer[x]++;
            }
        }
    }
    return answer;
}

Answer 1

问题分为两部分：

1) 确定群体

2) 计算每组人数

问题 1) 需要稳定器算法：

给每个单元格一个唯一的值
对于每对相邻单元格，将具有最高值的单元格更改为相邻单元格的（较低）值
重复上述直到不再发生变化

问题 2 变得相当简单，它只是所有出现值的频率 table

Java 中的连通分量标记

Connected Component Labeling in Java

java

arrays

multidimensional-array

connected-components