图中的最大匹配

Question

我有一个有趣的问题：
我的程序必须找到 1 的最大数量。 但这还不是全部！ 如果程序“看到”1，那么它应该清除1所在的整个列和行。

我遇到的问题：
我找不到 1 的最大数量，我不知道该怎么做。

我给你举了一个小例子，希望你能清楚。该程序必须像这样工作：

有一个矩阵：

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

程序找到1（位置[0][0]我已用黑色突出显示它），并清除行和列：

在此之后我们找到下一个 1、清除行列等：

最后，程序应打印黑色单元格的数量。

在我的示例中，它是 4

如何在 C++ 代码中执行此操作？请帮我！谢谢。

Answer 1

我更喜欢这样做（参见下面的代码）：使用两个“for”循环，并在第二个循环中使用条件“if”添加第三个“for”循环以设置为 0。

for(int i=0;i<m;i++)
    for(int j=0;j<n;j++)
    {
        if(cow[j][i]==1)
        {
            cnt++;
            for(int k=0;k<n;k++)
                cow[k][i]=cow[j][k]=0;
            break;
        }
    }

Answer 2

目前尚不清楚如何在矩阵中搜索“下一个”1，以及矩阵是否只能包含 0 和 1。但是，如果“下一个”有明确的定义，那么您只需按照您所描述的方式进行编码即可多于。可能的代码片段如下所示（未经测试，甚至未编译）：

 bool find_next_one(int&x, int&y, matrix const&M)
 {
   // next is in (col,row) order
   for(; x!=M.size(0); ++x)
     for(; y!=M.size(1); ++y)
       if(M(x,y)==1) return 1;
   return 0;
 }
 int count_one(matrix const&M_original)
 {
   matrix M(M_original); // make copy where we can set elements to 0
   int count=0;
   int x=0,y=0;
   while(find_next_one(x,y,M)) {
     ++count;
     for(int i=0; i!=M.size(1); ++i) M(x,i) = 0;
     for(int i=0; i!=M.size(0); ++i) M(i,y) = 0;
   }
   return count;
 }

Answer 3

注意到这看起来像矩阵奇点类型检查 - 特别是如果 1 和 0 是唯一要使用的东西。

您可以检查矩阵的行列式。非零意味着它等于行数和列数（如果矩阵始终是方阵）。如果 det(0)，则使用您想要将矩阵简化为简化形式的任何技术来查看有多少 0 列你有 - 或者只是先进行归约，然后沿着对角线计数。

哎呀，按附加值对列进行排序，将为您提供对角线形式。这将使检查 0 列变得非常容易。

Answer 4

我不会为您编写所有代码，但会提出一些建议来帮助您走上正轨。您应该了解如何迭代二维数组（矩阵）以及如何迭代该矩阵中的单个行或列。

给定一个（硬编码的）矩阵定义，如下所示：

struct Matrix4x4
{
    int        m[4][4];
};

要迭代所有元素，您需要编写如下内容：

   Matrix4x4 matrix;

   for (size_t row = 0; row < 4; ++row)
   {
       for (size_t col = 0; col < 4; ++col)
       {
           // do something with 'matrix.m[row][col]'
       }
   }

这将从左上角 (0,0) 到右下角 (3,3) 迭代矩阵。我假设这是您被告知要使用的遍历顺序。

要处理一行，您需要编写如下内容：

   void FunctionThatOperatesOnARow(Matrix4x4& matrix, size_t row)
   {
       for (size_t col = 0; col < 4; ++col)
       {
           // do something with 'matrix.m[row][col]'
       }
   }

要处理一列，您需要编写如下内容：

   void FunctionThatOperatesOnAColumn(Matrix4x4& matrix, size_t col)
   {
       for (size_t row = 0; row < 4; ++row)
       {
           // do something with 'matrix.m[row][col]'
       }
   }

现在您需要做的是修改迭代所有元素的代码的第一位，并让它检查是否为 1然后需要调用相应的函数来清除当前的列和行（可以基于后两个示例）。

对于最终结果，您只需在每次检测到 1 时增加本地计数器变量即可。