连通分量数

Question

计算矩阵中的连通分量数，表示M.给出M中两个坐标为X1，Y1和X2，Y2的项，如果

• M(x1，y1) == -1和
• M(x2，y2) == -1和
• X_1-x_2\x_(2)x_(2)x_(1)+_(2)~y_(2)，== _(1)

那么它们是相连的。示例：-1 0 -1 0 -1 0 -1 0 0 -1 0 0 0 -1 0 0 0 -1 0 0 -1 0 0 -1 0 0 0 -1 0 0 0 -1 0 0 0输出: 4。

我的想法是扫描矩阵。

Initialization:
count = 0.

对于矩阵中的每一项，执行以下三个测试。

1. 如果是0，跳过
2. 如果是-1，检查它的四个邻居。如果有一个邻居的值不是0和-1，则将该邻居的值赋值给当前项。否则，count++，ant然后将count分配给当前项。
3. 如果不是0和-1，则将当前项的值分配给其值为-1的四个邻居。

以下是我的代码：

int num_cc(int m[][COLS])
{
    int count = 0; 
    int r;
    int c;

    for(r = 0; r < ROWS; ++r)
    {
        for(c = 0; c < COLS; ++c)
        {
            if(m[r][c] == 0)
                continue;

            if(m[r][c] == -1)
            {
                if(r-1>=0 && m[r-1][c] > 0)
                    m[r][c] = m[r-1][c];
                else if(r+1<ROWS && m[r+1][c] > 0)
                    m[r][c] = m[r+1][c];
                else if(c-1>=0 && m[r][c-1] > 0)
                    m[r][c] = m[r][c-1];
                else if(c+1<COLS && m[r][c+1] > 0)
                    m[r][c] = m[r][c+1];
                else
                {
                    count++;
                    m[r][c] = count;
                }
            }

            if(m[r][c] > 0)
            {
                if(r-1>=0 && m[r-1][c] == -1)
                    m[r-1][c] = m[r][c];
                if(r+1<ROWS && m[r+1][c] == -1)
                    m[r+1][c] = m[r][c];
                if(c-1>=0 && m[r][c-1] == -1)
                    m[r][c-1] = m[r][c];
                if(c+1<COLS && m[r][c+1] == -1)
                    m[r][c+1] = m[r][c];       
            }

        }
    }

    return count;
}

有人能帮我核实一下吗？这是正确的吗？或者还有其他的解决方案？

Answer 1

风格:根据编码指南和首选项，您可能需要考虑将r和c的声明移到for-循环(for (int r = 0...)中，因为这些变量不应该在循环之外使用，因此，外部声明与此契约有一定的矛盾。

正确性:恐怕你贪婪的方法不太奏效--换句话说:它会产生错误的结果。考虑下面的矩阵(或者如果你用相反的方式循环它的对称变体)：

 0  0  0  0 -1
-1 -1 -1 -1 -1

通过首先遍历第一行，在行循环切换到第二行之前，将创建具有此中间结果的第一个连接组：

 0  0  0  0  1
-1 -1 -1 -1  1

接下来，内循环将找到另一个没有高编号邻居的-1单元，并创建第二个连接组件，尽管实际上只有一个。

简洁性:如果代码是正确的，那么您还可以删除循环中的所有if语句，但比较-1的语句除外。其他人的行为是多余的。