Chúng ta sẽ xem một bài toán ma trận Boolean thú vị. Cho một ma trận Boolean chứa 0 và 1. Mục tiêu là tìm vị trí có giá trị 1. Nếu 1 xuất hiện tại vị trí mat[i,j], ta sẽ đặt tất cả các phần tử của hàng i và cột j thành 1. Ví dụ: ma trận ban đầu:
1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0
Sau khi cập nhật:
1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1
Thuật toán
matrixUpdate(matrix[R,C])
bắt đầu định nghĩa hai mảng row[R] và col[C], điền 0 đánh dấu chỉ số hàng và cột của mat[R,C] nơi có 1 vào row[R] và col[C] kiểm tra row[R] và col[C] nếu vị trí được đánh dấu, điền 1 cho toàn bộ hàng và cột đó kết thúc
Ví dụ
#include <iostream>
#define R 4
#define C 4
using namespace std;
void updateMatrix(bool mat[R][C]) {
bool row[R];
bool col[C];
int i, j;
for (int i = 0; i < R; i++) { // đặt tất cả phần tử row = 0
row[i] = 0;
}
for (i = 0; i < C; i++) { // đặt tất cả phần tử col = 0
col[i] = 0;
}
for (int i = 0; i < R; i++) { // đánh dấu row và col để xác định vị trí 1
for (int j = 0; j < C; j++) {
if (mat[i][j] == 1) {
row[i] = 1;
col[j] = 1;
}
}
}
for (i = 0; i < R; i++) { // đặt 1 cho hàng và cột nơi được đánh dấu
for (j = 0; j < C; j++) {
if (row[i] == 1 || col[j] == 1) {
mat[i][j] = 1;
}
}
}
}
void displayMatrix(bool mat[R][C]) {
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
cout << mat[i][j];
}
cout << endl;
}
}
int main() {
bool mat[R][C] = { {1, 0, 0, 1},
{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 1, 0, 0} };
cout << "Given Matrix" << endl;
displayMatrix(mat);
updateMatrix(mat);
cout << "Updated Matrix" << endl;
displayMatrix(mat);
return 0;
}
Kết quả
Given Matrix 1001 0000 0000 0100 Updated Matrix 1111 1101 1101 1111