Tìm hình chữ nhật có 4 góc bằng 1 trong ma trận nhị phân C++

Cho ma trận nhị phân. Kiểm tra xem có tồn tại hình chữ nhật nào có 4 đỉnh đều bằng 1 hay không. Ví dụ ma trận 4×5 có hình chữ nhật với 4 góc là 1.

Giải thuật băm cặp cột

Duyệt từng hàng. Với mỗi hàng, tìm tất cả cặp cột (j, k) mà cả hai đều bằng 1. Lưu cặp này vào bảng băm. Nếu gặp lại cặp cột này ở hàng sau, đã tìm thấy hình chữ nhật.

Ví dụ minh họa

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;

bool hasRectangle(const vector>& mat) {
    int rows = mat.size();
    if (rows == 0) return false;
    int cols = mat[0].size();
    
    unordered_map> table;
    
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols-1; j++) {
            for (int k = j+1; k < cols; k++) {
                if (mat[i][j] == 1 && mat[i][k] == 1) {
                    if (table[j].count(k) || table[k].count(j))
                        return true;
                    table[j].insert(k);
                    table[k].insert(j);
                }
            }
        }
    }
    return false;
}

int main() {
    vector> mat = {
        {1,0,0,1,0},
        {0,0,1,0,1},
        {0,0,0,1,0},
        {1,0,1,0,1}
    };
    cout << (hasRectangle(mat) ? "Có hình chữ nhật" : "Không có hình chữ nhật");
    return 0;
}

Kết quả

Có hình chữ nhật