数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学使用 C++ 设置二进制矩阵所有元素所需的最少操作次数
问题陈述
给定一个 N 行 M 列的二进制矩阵。允许对矩阵进行的操作是选择任何索引 (x, y)，并切换左上角为 (0, 0) 且右下角为 (x-1, y-1) 的矩形内的所有元素。切换元素意味着将 1 更改为 0，将 0 更改为 1。任务是找到使矩阵所有元素都设置为 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) 以使整个矩阵仅包含 1。
算法
其思想是从终点 (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
更新于：2019年11月22日
163 次查看
广告