資料結構
網路
關係資料庫管理系統 (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 次檢視
廣告