ค้นหาว่ามีสี่เหลี่ยมผืนผ้าในเมทริกซ์ไบนารีที่มีมุมเป็น 1 ใน C++ . หรือไม่

สมมติว่าเรามีเมทริกซ์ไบนารี เราต้องค้นหาว่ามีสี่เหลี่ยมหรือลำดับใดๆ ในเมทริกซ์ที่กำหนดที่มีมุมทั้งสี่เท่ากับ 1 หรือไม่ เมทริกซ์จะเหมือน

ผลลัพธ์จะเป็นใช่ มีสี่เหลี่ยมผืนผ้าหนึ่งรูปซึ่งมีมุมอยู่ 1 วินาที

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

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

• สำหรับแต่ละบรรทัด ให้จำแต่ละชุดของ 1 สองตัวแล้วดันเป็นชุดแฮช

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

ตัวอย่าง

#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