在C ++中设置二进制矩阵的所有元素所需的最少操作
问题陈述
给定N行和M列的二进制矩阵。矩阵上允许的操作是选择任何索引(x,y)并在左上角为(0,0)和右下角为(x-1,y-1)的矩形之间切换所有元素。切换元素意味着将1更改为0，将0更改为1。任务是找到对矩阵的所有元素进行置位（即，使所有元素均为1）所需的最小操作。
示例
If input matrix is {0, 0, 0, 1, 1}
{0, 0, 0, 1, 1}
{0, 0, 0, 1, 1}
{1, 1, 1, 1, 1}
{1, 1, 1, 1, 1}
Then answer is 1一口气选择(3,3)使整个矩阵仅包含1s。
算法
这个想法是从端点（N–1，M–1）开始，然后以相反的顺序遍历矩阵。每当我们遇到一个值为0的单元格时，将其翻转
示例
#include <iostream>
#define ROWS 5
#define COLS 5
using namespace std;
int getMinOperations(bool arr[ROWS][COLS]) {
int ans = 0;
for (int i = ROWS - 1; i >= 0; i--){
for (int j = COLS - 1; j >= 0; j--){
if(arr[i][j] == 0){
ans++;
for (int k = 0; k <= i; k++){
for (int h = 0; h <= j; h++){
if (arr[k][h] == 1)
arr[k][h] = 0;
else
arr[k][h] = 1;
}
}
}
}
}
return ans;
}
int main() {
bool mat[ROWS][COLS] = {
0, 0, 1, 1, 1,
0, 0, 0, 1, 1,
0, 0, 0, 1, 1,
1, 1, 1, 1, 1,
1, 1, 1, 1, 1
};
cout << "Minimum required operations = " << getMinOperations(mat) << endl;
return 0;
}输出结果
当您编译并执行上述程序时。它产生以下输出-
Minimum required operations = 3