Ma trận Boolean (Boolean Matrix) trong C++

Ma trận Boolean chỉ chứa 0 và 1. Cho ma trận m x n. Nếu mat[i][j] = 1 thì toàn bộ hàng i và cột j được đặt thành 1.

Ví dụ: {{1,0},{0,0}} -> {{1,1},{1,0}}.

Thuật toán tối ưu O(m*n) không dùng bộ nhớ thêm:

• Dùng hàng 0 và cột 0 làm cờ (flag).
• Duyệt ma trận, nếu mat[i][j]==1 -> mat[0][j]=1, mat[i][0]=1.
• Lưu cờ riêng cho hàng 0 và cột 0 ban đầu.
• Duyệt lại từ (1,1), nếu mat[0][j]||mat[i][0] -> mat[i][j]=1.
• Cuối cùng xử lý hàng 0 và cột 0 theo cờ lưu.

Ví dụ code

#include <bits/stdc++.h>
using namespace std;

const int R = 3, C = 4;

void matrixFlip(int mat[R][C]) {
    int rowFlag = 0, colFlag = 0;
    // Bước 1: kiểm tra hàng 0, cột 0 ban đầu
    for (int j = 0; j < C; j++) if (mat[0][j] == 1) rowFlag = 1;
    for (int i = 0; i < R; i++) if (mat[i][0] == 1) colFlag = 1;
    // Bước 2: dùng hàng 0, cột 0 làm cờ cho các ô còn lại
    for (int i = 1; i < R; i++)
        for (int j = 1; j < C; j++)
            if (mat[i][j] == 1) {
                mat[0][j] = 1;
                mat[i][0] = 1;
            }
    // Bước 3: cập nhật ma trận dựa trên cờ
    for (int i = 1; i < R; i++)
        for (int j = 1; j < C; j++)
            if (mat[0][j] == 1 || mat[i][0] == 1)
                mat[i][j] = 1;
    // Bước 4: xử lý hàng 0, cột 0
    if (rowFlag) for (int j = 0; j < C; j++) mat[0][j] = 1;
    if (colFlag) for (int i = 0; i < R; i++) mat[i][0] = 1;
}

int main() {
    int mat[R][C] = {{1,0,0,0},{0,0,0,0},{0,0,1,0}};
    cout << "Input:\n";
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) cout << mat[i][j] << " ";
        cout << endl;
    }
    matrixFlip(mat);
    cout << "Output:\n";
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) cout << mat[i][j] << " ";
        cout << endl;
    }
    return 0;
}

Kết quả

Input:
1 0 0 0
0 0 0 0
0 0 1 0
Output:
1 1 1 1
1 0 1 0
1 1 1 1