Boolean Matrix (เมทริกซ์บูลีน) ใน C++

บทนำ

Boolean Matrix คือเมทริกซ์ที่มีค่าแค่ 0 และ 1 โจทย์: ถ้า m[i][j] = 1 ให้เซตแถว i ทั้งแถวและคอลัมน์ j ทั้งคอลัมน์ เป็น 1

ตัวอย่าง

Input: {{1,0},{0,0}} → Output: {{1,1},{1,0}}

เพราะ m[0][0]=1 → row 0 และ col 0 กลายเป็น 1 ทั้งหมด

อัลกอริทึม (Space Optimized)

1. ใช้แถวแรกและคอลัมน์แรกเป็น flag array
2. row_flag, col_flag เก็บว่าแถวแรก/คอลัมน์แรกเดิมมี 1 หรือไม่
3. วนลูปเมทริกซ์ ถ้าเจอ 1 → mat[0][j]=1, mat[i][0]=1
4. วนลูปอีกครั้ง (เริ่ม 1,1) ถ้า mat[0][j]==1 หรือ mat[i][0]==1 → mat[i][j]=1
5. สุดท้ายจัดการแถวแรกและคอลัมน์แรกตาม flag

ตัวอย่างโค้ด C++

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

const int R = 3;
#define C 4

void matrixflip(int mat[R][C]) {
    int row_flag = 0, col_flag = 0;
    
    // ตรวจสอบแถวแรกและคอลัมน์แรกเดิม
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (i == 0 && mat[i][j] == 1) row_flag = 1;
            if (j == 0 && mat[i][j] == 1) col_flag = 1;
            if (mat[i][j] == 1) {
                mat[0][j] = 1;
                mat[i][0] = 1;
            }
        }
    }
    
    // อัปเดตภายในเมทริกซ์
    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;
    
    // จัดการแถวแรกและคอลัมน์แรก
    if (row_flag) for (int i = 0; i < C; i++) mat[0][i] = 1;
    if (col_flag) 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 Matrix:\n";
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) cout << mat[i][j] << " ";
        cout << endl;
    }
    matrixflip(mat);
    cout << "\nMatrix after flip:\n";
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) cout << mat[i][j] << " ";
        cout << endl;
    }
    return 0;
}

ผลลัพธ์

Input Matrix:
1 0 0 0
0 0 0 0
0 0 1 0

Matrix after flip:
1 1 1 1
1 0 1 0
1 1 1 1