在图表中最大匹配

-1

我有一个有趣的问题：
我的程序必须找到最大数量1。但那不是全部！如果程序已经“看到” 1，那么就应该清除整个列和行其中1所在。在图表中最大匹配

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

为了你，我做了一个小例子，我希望这将是清楚的给你。该程序必须像这样工作：

有一个矩阵：

程序发现1（位置[0][0]我突出它黑色），并清除行和列：

Example 2

此之后，我们找到下一个1，清除行和columnand等：

Example 3

在结束时，程序应该打印黑细胞的数目。

在我的例子是4

如何做到在C++代码？请帮帮我！谢谢。

来源

2011-11-18 Kamil Hismatullin

请发布一些你已经尝试过的代码。这个社区是用来帮助那些没有编写所有代码的代码。 –

这是功课吗？ – Amy

我不明白。你是否需要清理矩阵，使得矩阵的数量最大，或者你只需要迭代低谷，在找到东西的时候删除东西，最后计算你找到了多少东西？前一个我觉得有点困难。 – SinistraD

我喜欢做这样的（见下面的代码）：使用两节“for”循环和第二内侧使用条件“如果”添加第三个“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; 
     } 
    }

来源

2012-10-23 16:51:28 Kubra

目前尚不清楚如何寻找你的矩阵中的“下一个” 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; 
}

来源

2011-11-18 19:10:43 Walter

注意到这看起来像一个矩阵奇异类型检查 - 特别是如果1和0将被使用的唯一的事情。

您可以检查矩阵的形式决定。非零意味着它等于行和列的数量（如果矩阵总是正方形的话）。如果det（0），则使用任何你想使矩阵向下缩减的方法来查看有多少个0列你有 - 或者只是先减少，然后走对角线计数。

哎呀通过其附加值排序列，将其放在对角线的形式为您服务。这将使得它也很容易检查0列。

来源

2011-11-18 19:18:14

我不会写所有的代码你，但会建议一些事情让你的轨道上。您应该了解如何遍历二维数组（矩阵）以及如何迭代该矩阵内的单个行或列。

由于矩阵的（硬编码）的定义，看起来像这样：

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.

来源

2011-11-18 19:33:53

在图表中最大匹配

回答

相关问题