ตรวจสอบว่ามีสี่เหลี่ยมใน Binary Matrix ที่มุมทั้ง 4 เป็น 1 ใน C++

คำอธิบายปัญหา

สมมติว่าเรามี binary matrix เราต้องหาว่ามีสี่เหลี่ยมผืนผ้า (rectangle) หรือลำดับใดในเมทริกซ์ที่มุมทั้งสี่เท่ากับ 1 หรือไม่ เมทริกซ์เป็นแบบนี้:

ผลลัพธ์จะเป็น yes ที่นี่มีสี่เหลี่ยมผืนผ้าหนึ่งที่มุมเป็น 1

เพื่อแก้ปัญหานี้ เราจะใช้วิธีที่มีประสิทธิภาพ เราจะทำตามขั้นตอนเหล่านี้:

• สแกนเมทริกซ์จากบนลงล่าง บรรทัดต่อบรรทัด

• สำหรับแต่ละบรรทัด จำทุกคู่ของ 1 สองตัว และเก็บไว้ใน hash-set

• ถ้าเราพบคู่นั้นอีกครั้งในบรรทัดต่อไป เราจะได้สี่เหลี่ยมผืนผ้าของเรา

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

#include<iostream> #include<unordered_set> #include<unordered_map> #include<vector> using namespace std; bool isRectanglePresent(const vector<vector<int> >& matrix) {    int rows = matrix.size();    if (rows == 0)    return false;    int columns = matrix[0].size();    unordered_map<int, unordered_set<int> > table;    for (int i = 0; i < rows; ++i) {       for (int j = 0; j < columns - 1; ++j) {          for (int k = j + 1; k < columns; ++k) {             if (matrix[i][j] == 1 && matrix[i][k] == 1) {                if (table.find(j) != table.end() && table[j].find(k) != table[j].end())                   return true;                if (table.find(k) != table.end() && table[k].find(j) != table[k].end())                   return true;                table[j].insert(k);                table[k].insert(j);             }          }       }    }    return false; } int main() {    vector<vector<int> > matrix = {       { 1, 0, 0, 1, 0 },       { 0, 0, 1, 0, 1 },       { 0, 0, 0, 1, 0 },       { 1, 0, 1, 0, 1 }    };    if (isRectanglePresent(matrix))       cout << "Rectangle is present";    else       cout << "Rectangle is not present"; }

ผลลัพธ์

Rectangle is present