# 查找二進制矩陣中是否有一個角為 1 的矩形 > 原文： [https://www.geeksforgeeks.org/find-rectangle-binary-matrix-corners-1/](https://www.geeksforgeeks.org/find-rectangle-binary-matrix-corners-1/) 有給定的二進制矩陣，我們需要查找給定矩陣中是否存在所有四個角均等于 1 的矩形或正方形。 **示例**： ``` Input : mat[][] = { 1 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 1 0 1} Output : Yes as there exists- 1 0 1 0 1 0 1 0 1 ``` **暴力方法-** 每當我們在任意索引處找到 1 時，我們便開始掃描矩陣，然后嘗試尋找所有可以形成矩形的索引組合。 算法- ``` for i = 1 to rows for j = 1 to columns if matrix[i][j] == 1 for k=i+1 to rows for l=j+1 to columns if (matrix[i][k]==1 && matrix[l][i]==1 && m[l][k]==1) return true return false ``` **時間復雜度**： O（m ^ 2 * n ^ 2） ## C++ ```cpp // A brute force approach based CPP program to // find if there is a rectangle with 1 as corners. #include <bits/stdc++.h> using namespace std; // Returns true if there is a rectangle with // 1 as corners. bool isRectangle(const vector<vector<int> >& m) { ????// finding row and column size ????int rows = m.size(); ????if (rows == 0) ????????return false; ????int columns = m[0].size(); ????// scanning the matrix ????for (int y1 = 0; y1 < rows; y1++) ????????for (int x1 = 0; x1 < columns; x1++) ????????????// if any index found 1 then try ????????????// for all rectangles ????????????if (m[y1][x1] == 1) ????????????????for (int y2 = y1 + 1; y2 < rows; y2++) ????????????????????for (int x2 = x1 + 1; x2 < columns; x2++) ????????????????????????if (m[y1][x2] == 1 && m[y2][x1] == 1 && m[y2][x2] == 1) ????????????????????????????return true; ????return false; } // Driver code int main() { ????vector<vector<int> > mat = { { 1, 0, 0, 1, 0 }, ?????????????????????????????????{ 0, 0, 1, 0, 1 }, ?????????????????????????????????{ 0, 0, 0, 1, 0 }, ?????????????????????????????????{ 1, 0, 1, 0, 1 } }; ????if (isRectangle(mat)) ????????cout << "Yes"; ????else ????????cout << "No"; } ``` ## Java ```java // A brute force approach based CPP program to // find if there is a rectangle with 1 as corners. public class FindRectangle { ????// Returns true if there is a rectangle with ????// 1 as corners. ????static boolean isRectangle(int m[][]) ????{ ????????// finding row and column size ????????int rows = m.length; ????????if (rows == 0) ????????????return false; ????????int columns = m[0].length; ????????// scanning the matrix ????????for (int y1 = 0; y1 < rows; y1++) ????????????for (int x1 = 0; x1 < columns; x1++) ????????????????// if any index found 1 then try ????????????????// for all rectangles ????????????????if (m[y1][x1] == 1) ????????????????????for (int y2 = y1 + 1; y2 < rows; y2++) ????????????????????????for (int x2 = x1 + 1; x2 < columns; x2++) ????????????????????????????if (m[y1][x2] == 1 && m[y2][x1] == 1 && m[y2][x2] == 1) ????????????????????????????????return true; ????????return false; ????} ????public static void main(String args[]) ????{ ????????int mat[][] = { { 1, 0, 0, 1, 0 }, ????????????????????????{ 0, 0, 1, 0, 1 }, ????????????????????????{ 0, 0, 0, 1, 0 }, ????????????????????????{ 1, 0, 1, 0, 1 } }; ????????if (isRectangle(mat)) ????????????System.out.print("Yes"); ????????else ????????????System.out.print("No"); ????} } // This code is contributed by Gaurav Tiwari ``` ## Python3 ```py # A brute force approach based Python3 program to # find if there is a rectangle with 1 as corners. # Returns true if there is a rectangle? # with 1 as corners. def isRectangle(m): ????# finding row and column size ????rows = len(m) ????if (rows == 0): ????????return False ????columns = len(m[0]) ????# scanning the matrix ????for y1 in range(rows): ????????for x1 in range(columns): ????????????# if any index found 1 then? ????????????# try for all rectangles ????????????if (m[y1][x1] == 1): ????????????????for y2 in range(y1 + 1, rows): ????????????????????for x2 in range(x1 + 1, columns): ????????????????????????if (m[y1][x2] == 1 and? ????????????????????????????m[y2][x1] == 1 and? ????????????????????????????m[y2][x2] == 1): ????????????????????????????return True ????return False # Driver code mat = [[1, 0, 0, 1, 0], ???????[0, 0, 1, 0, 1], ???????[0, 0, 0, 1, 0], ???????[1, 0, 1, 0, 1]] if (isRectangle(mat)): ????print("Yes") else: ????print("No") # This code is conteibuted # by mohit kumar 29 ``` ## C# ```cs // A brute force approach based C# program to // find if there is a rectangle with 1 as corners. using System; public class FindRectangle { ????// Returns true if there is a rectangle with ????// 1 as corners. ????static Boolean isRectangle(int[, ] m) ????{ ????????// finding row and column size ????????int rows = m.GetLength(0); ????????if (rows == 0) ????????????return false; ????????int columns = m.GetLength(1); ????????// scanning the matrix ????????for (int y1 = 0; y1 < rows; y1++) ????????????for (int x1 = 0; x1 < columns; x1++) ????????????????// if any index found 1 then try ????????????????// for all rectangles ????????????????if (m[y1, x1] == 1) ????????????????????for (int y2 = y1 + 1; y2 < rows; y2++) ????????????????????????for (int x2 = x1 + 1; x2 < columns; x2++) ????????????????????????????if (m[y1, x2] == 1 && m[y2, x1] == 1 && m[y2, x2] == 1) ????????????????????????????????return true; ????????return false; ????} ????// Driver code ????public static void Main(String[] args) ????{ ????????int[, ] mat = { { 1, 0, 0, 1, 0 }, ????????????????????????{ 0, 0, 1, 0, 1 }, ????????????????????????{ 0, 0, 0, 1, 0 }, ????????????????????????{ 1, 0, 1, 0, 1 } }; ????????if (isRectangle(mat)) ????????????Console.Write("Yes"); ????????else ????????????Console.Write("No"); ????} } // This code contributed by Rajput-Ji ``` **輸出**： ``` Yes ``` **有效方法** –從上到下，逐行掃描 –對于每一行，請記住 2 1 的每種組合并將其推入哈希集 –如果我們 在下一行中再次找到該組合，我們得到矩形 **時間復雜度**： O（n * m ^ 2） ## C++ ``` // An efficient approach based CPP program to // find if there is a rectangle with 1 as // corners. #include <bits/stdc++.h> using namespace std; // Returns true if there is a rectangle with // 1 as corners. bool isRectangle(const vector<vector<int> >& matrix) { ????// finding row and column size ????int rows = matrix.size(); ????if (rows == 0) ????????return false; ????int columns = matrix[0].size(); ????// map for storing the index of combination of 2 1's ????unordered_map<int, unordered_set<int> > table; ????// scanning from top to bottom line by line ????for (int i = 0; i < rows; ++i) { ????????for (int j = 0; j < columns - 1; ++j) { ????????????for (int k = j + 1; k < columns; ++k) { ????????????????// if found two 1's in a column ????????????????if (matrix[i][j] == 1 && matrix[i][k] == 1) { ????????????????????// check if there exists 1's in same ????????????????????// row previously then return true ????????????????????// we don't need to check (j, k) pair ????????????????????// and again (k, j) pair because we always ????????????????????// store pair in ascending order and similarly ????????????????????// check in ascending order, i.e. j always less ????????????????????// than k. ????????????????????if (table.find(j) != table.end() ????????????????????????&& table[j].find(k) != table[j].end()) ????????????????????????return true; ????????????????????// store the indexes in hashset ????????????????????table[j].insert(k); ????????????????} ????????????} ????????} ????} ????return false; } // Driver code int main() { ????vector<vector<int> > mat = { { 1, 0, 0, 1, 0 }, ?????????????????????????????????{ 0, 1, 1, 1, 1 }, ?????????????????????????????????{ 0, 0, 0, 1, 0 }, ?????????????????????????????????{ 1, 1, 1, 1, 0 } }; ????if (isRectangle(mat)) ????????cout << "Yes"; ????else ????????cout << "No"; } // This code is improved by Gautam Agrawal ```