C++ 中最多翻转二进制矩阵 K 次后的最大分数

在这个问题中，我们给定一个由布尔值（即 0 和 1）组成的二维数组 arr[] 和一个整数 K。我们的任务是创建一个程序，在 C++ 中找到最多翻转二进制矩阵 K 次后的最大分数。

问题描述 - 在这里，对于二维数组和 k 次移动，我们需要找到由数组元素创建的数字。在每次移动中，我们将取一行或一列并翻转该行或列的所有元素。将进行选择以记住我们需要最大化在矩阵的行中进行 K 次翻转后创建的数字。我们需要返回每一行创建的所有数字的总和。

让我们举一个例子来理解这个问题，

输入

arr[][] = {
   {1, 0, 0},
   {0, 1, 1},
   {1, 0, 1}
}
K = 2

输出

19

解释

我们有两次翻转，

第一次翻转 - 我们将翻转第 2 行的元素。这将使数组变为，

{{1, 0, 0},
{1, 0, 0},
{1, 0, 1}}

第二次翻转 - 我们将翻转第 2 列的元素。这将使数组变为，

{{1, 1, 0},
{1, 1, 0},
{1, 1, 1}}

每一行创建的最终数字为 6、6、7。

Maximum sum = 19.

解决方案方法

为了解决这个问题，我们需要首先使第一列的元素为 1。因为第 i 列的 1 将贡献 2i，这将是最大的可能数字（如果考虑一个设置位）。因此，最左边的列需要具有最大数量的 1（设置位）以使总和最大化。然后，我们将转到每一行的其他元素。

要检查是否需要翻转行或列。我们需要检查该列中的其他值。即所有行的第一个元素。如果 0 的数量大于 1 的数量。我们将翻转列，否则翻转行。

为了解决这个问题，我们将使用 map 数据结构。

程序说明我们解决方案的工作原理，

示例

 在线演示

#include <bits/stdc++.h>
using namespace std;
const int row = 3;
const int col = 3;
int MaxSumAfterFlip(int mat[row][col], int K) {
   map<int, int> flipValues;
   int updateVal, MaxSum = 0;
   for (int i = 0; i < row; ++i) {
      if (mat[i][0] == 0) {
         updateVal = 0;
         for (int j = 1; j < col; ++j)
            updateVal = updateVal + mat[i][j] * pow(2, col - j- 1);
         flipValues[updateVal] = i;
      }
   }
   map<int, int>::iterator it = flipValues.begin();
   while (K > 0 && it != flipValues.end()) {
      int updateIndex = it->second ;
      for (int j = 0; j < col; ++j)
         mat[updateIndex][j] = (mat[updateIndex][j] + 1) % 2;
      it++;
      K--;
   }
   MaxSum = 0;
   int zeros, ones = 0;
   for (int j = 0; j < col; ++j) {
      zeros = ones = 0;
      for (int i = 0; i < row; ++i) {
         mat[i][j] == 0 ? zeros++ : ones++;
      }
      if (K > 0 && zeros > ones) {
         MaxSum += zeros * pow(2, (col - j - 1));
         K--;
      }
      else
         MaxSum += ones * pow(2, (col - j - 1));
   }
   return MaxSum;
}
int main() {
   int mat[row][col] = {{1, 0, 0 },{0, 1, 1},{1, 0, 1}};
   int K = 2;
   cout<<"The Maximum score after flipping the matrix atmost K times is "<<MaxSumAfterFlip(mat, K);
   return 0;
}

输出

The Maximum score after flipping the matrix atmost K times is 19

Ayush Gupta

更新于: 2020 年 9 月 15 日

265 次查看

开启您的 职业生涯

通过完成课程获得认证

开始学习