Trong bài toán này, chúng ta được cung cấp một mảng 2-D arr [] bao gồm các giá trị boolean (tức là 0 và 1) và một số nguyên K. Nhiệm vụ của chúng ta là tạo một chương trình để tìm điểm Tối đa sau khi lật Ma trận nhị phân ít nhất K lần trong C ++.
Mô tả sự cố - Ở đây, đối với mảng 2-D và k di chuyển, chúng ta cần tìm số được tạo bởi các phần tử của mảng. Trong mỗi lần di chuyển, chúng ta sẽ lấy một hàng hoặc cột và lật tất cả các phần tử của hàng hoặc cột. Sự lựa chọn sẽ được thực hiện để lưu ý rằng chúng ta cần tối đa hóa số được tạo ra sau khi K lật được thực hiện trong một hàng của ma trận. Và chúng ta cần trả về tổng của tất cả các số được tạo trong hàng.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr[][] = {
{1, 0, 0},
{0, 1, 1},
{1, 0, 1}
}
K = 2 Đầu ra
19
Giải thích
Chúng tôi có hai lần lật,
Lần lật đầu tiên - chúng ta sẽ lật các phần tử ở hàng thứ hai. Điều này sẽ làm cho mảng,
{{1, 0, 0},
{1, 0, 0},
{1, 0, 1}} Lần lật thứ hai - chúng ta sẽ lật các phần tử của cột thứ hai. Điều này sẽ làm cho mảng,
{{1, 1, 0},
{1, 1, 0},
{1, 1, 1}} Số cuối cùng được tạo ở mỗi hàng là 6, 6, 7.
Maximum sum = 19.
Phương pháp tiếp cận giải pháp
Để giải quyết vấn đề, chúng ta cần đặt phần tử của cột đầu tiên là 1. Như 1 ở cột thứ i sẽ đóng góp cho 2i, đây sẽ là số lớn nhất có thể (nếu xem xét một bit đặt). Vì vậy, cột ngoài cùng bên trái cần có số lượng tối đa là 1 (bit đặt) để làm cho tổng là tối đa. Sau đó, chúng ta sẽ tìm các phần tử khác của mỗi hàng.
Để kiểm tra xem tôi có cần lật hàng hoặc cột hay không. Chúng ta cần kiểm tra các giá trị khác trong cột. tức là tất cả các phần tử đầu tiên của các hàng. Nếu số lượng của 0 lớn hơn số 1. Chúng tôi sẽ lật cột nếu không sẽ lật hàng.
Để giải quyết vấn đề, chúng tôi sẽ sử dụng cấu trúc dữ liệu bản đồ.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#include <bits/stdc++.h>
using namespace std;
const int row = 3;
const int col = 3;
int MaxSumAfterFlip(int mat[row][col], int K) {
map<int, int> flipValues;
int updateVal, MaxSum = 0;
for (int i = 0; i < row; ++i) {
if (mat[i][0] == 0) {
updateVal = 0;
for (int j = 1; j < col; ++j)
updateVal = updateVal + mat[i][j] * pow(2, col - j- 1);
flipValues[updateVal] = i;
}
}
map<int, int>::iterator it = flipValues.begin();
while (K > 0 && it != flipValues.end()) {
int updateIndex = it->second ;
for (int j = 0; j < col; ++j)
mat[updateIndex][j] = (mat[updateIndex][j] + 1) % 2;
it++;
K--;
}
MaxSum = 0;
int zeros, ones = 0;
for (int j = 0; j < col; ++j) {
zeros = ones = 0;
for (int i = 0; i < row; ++i) {
mat[i][j] == 0 ? zeros++ : ones++;
}
if (K > 0 && zeros > ones) {
MaxSum += zeros * pow(2, (col - j - 1));
K--;
}
else
MaxSum += ones * pow(2, (col - j - 1));
}
return MaxSum;
}
int main() {
int mat[row][col] = {{1, 0, 0 },{0, 1, 1},{1, 0, 1}};
int K = 2;
cout<<"The Maximum score after flipping the matrix atmost K times is "<<MaxSumAfterFlip(mat, K);
return 0;
} Đầu ra
The Maximum score after flipping the matrix atmost K times is 19