在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
热门推荐
10 读书祝福语女生短句简短
11 感谢同事新婚祝福语简短
12 感谢教官文案祝福语简短
13 员工聚会蛋糕祝福语简短
14 元宵发客户祝福语简短
15 给团队信心祝福语简短
16 医美的祝福语大全简短
17 异国姻缘的祝福语简短
18 兄妹拍照祝福语简短的话