Tuyên bố vấn đề
Cho một ma trận nhị phân gồm N hàng và M cột. Thao tác được phép trên ma trận là chọn bất kỳ chỉ mục nào (x, y) và chuyển đổi tất cả các phần tử giữa hình chữ nhật có góc trên bên trái là (0, 0) và dưới cùng bên phải là (x-1, y-1). Chuyển đổi phần tử có nghĩa là thay đổi 1 thành 0 và 0 thành 1. Nhiệm vụ là tìm các phép toán tối thiểu cần thiết để thiết lập tất cả các phần tử của ma trận, tức là đặt tất cả các phần tử thành 1.
Ví dụ
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 Trong một lần di chuyển, hãy chọn (3, 3) để tạo toàn bộ ma trận chỉ gồm 1s.
Thuật toán
Ý tưởng là bắt đầu từ điểm cuối (N - 1, M - 1) và duyệt ma trận theo thứ tự ngược lại. Bất cứ khi nào chúng ta gặp một ô có giá trị 0, hãy lật nó
Ví dụ
#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;
} Đầu ra
Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -
Minimum required operations = 3