Đề bài
Cho ma trận nhị phân N hàng và M cột. Phép toán cho phép trên ma trận là chọn bất kỳ chỉ số (x, y) và đảo ngược tất cả các phần tử trong hình chữ nhật có góc trên bên trái là (0, 0) và góc dưới bên phải là (x-1, y-1). Đảo ngược phần tử nghĩa là thay 1 thành 0 và 0 thành 1. Nhiệm vụ là tìm số phép toán tối thiểu để đặt tất cả các phần tử của ma trận thành 1.
Ví dụ
Nếu ma trận đầu vào là
{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}
Thì câu trả lời là 1
Trong một nước đi, chọn (3, 3) để làm cho toàn bộ ma trận chỉ chứa 1.
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. Bất cứ khi nào gặp ô 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 << "Số phép toán tối thiểu = " << getMinOperations(mat) << endl;
return 0;
}
Kết quả
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:
Số phép toán tối thiểu = 3