有一个给定的二元矩阵，我们需要找出在给定的矩阵中是否存在四个角都相等的矩形或正方形
null
例如：
Input :mat[][] = { 1 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 1 0 1}Output : Yesas there exists-1 0 10 1 01 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][l]==1 && matrix[k][j]==1 && m[k][l]==1) return truereturn false
C++
// 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
// 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
# 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 contributed # by mohit kumar 29 |
C#
// 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 |
Javascript
<script> // A brute force approach based Javascript program to // find if there is a rectangle with 1 as corners. // Returns true if there is a rectangle with // 1 as corners. function isRectangle(m) { // finding row and column size let rows = m.length; if (rows == 0) return false ; let columns = m[0].length; // scanning the matrix for (let y1 = 0; y1 < rows; y1++) for (let x1 = 0; x1 < columns; x1++) // if any index found 1 then try // for all rectangles if (m[y1][x1] == 1) for (let y2 = y1 + 1; y2 < rows; y2++) for (let x2 = x1 + 1; x2 < columns; x2++) if (m[y1][x2] == 1 && m[y2][x1] == 1 && m[y2][x2] == 1) return true ; return false ; } let mat = [[1, 0, 0, 1, 0], [0, 0, 1, 0, 1], [0, 0, 0, 1, 0], [1, 0, 1, 0, 1]]; if (isRectangle(mat)) document.write( "Yes" ); else document.write( "No" ); // This code is contributed by patel2127 </script> |
输出
Yes
时间复杂性： O（m） 2. *n 2. )
有效的方法
- 从上到下逐行扫描
- 对于每一行，记住2个1的每个组合，并将其放入一个哈希集中
- 如果我们在后面的一行中再次找到这个组合，我们就得到了矩形
以下是上述方法的实施情况：
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 |
JAVA
// An efficient approach based Java program to // find if there is a rectangle with 1 as // corners. import java.util.HashMap; import java.util.HashSet; public class FindRectangle { // Returns true if there is a rectangle with // 1 as corners. static boolean isRectangle( int matrix[][]) { // finding row and column size int rows = matrix.length; if (rows == 0 ) return false ; int columns = matrix[ 0 ].length; // map for storing the index of combination of 2 1's HashMap<Integer, HashSet<Integer> > table = new HashMap<>(); // 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 if (table.containsKey(j) && table.get(j).contains(k)) { return true ; } if (table.containsKey(k) && table.get(k).contains(j)) { return true ; } // store the indexes in hashset if (!table.containsKey(j)) { HashSet<Integer> x = new HashSet<>(); x.add(k); table.put(j, x); } else { table.get(j).add(k); } if (!table.containsKey(k)) { HashSet<Integer> x = new HashSet<>(); x.add(j); table.put(k, x); } else { table.get(k).add(j); } } } } } 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
# An efficient approach based Python 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(matrix): # finding row and column size rows = len (matrix) if (rows = = 0 ): return False columns = len (matrix[ 0 ]) # map for storing the index of # combination of 2 1's table = {} # scanning from top to bottom # line by line for i in range (rows): for j in range (columns - 1 ): for k in range (j + 1 , columns): # if found two 1's in a column if (matrix[i][j] = = 1 and matrix[i][k] = = 1 ): # check if there exists 1's in same # row previously then return true if (j in table and k in table[j]): return True if (k in table and j in table[k]): return True # store the indexes in hashset if j not in table: table[j] = set () if k not in table: table[k] = set () table[j].add(k) table[k].add(j) return False # Driver Code if __name__ = = '__main__' : 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 contributed # by SHUBHAMSINGH10 |
C#
// An efficient approach based C# program to // find if there is a rectangle with 1 as // corners. using System; using System.Collections.Generic; public class FindRectangle { // Returns true if there is a rectangle with // 1 as corners. static bool isRectangle( int [, ] matrix) { // finding row and column size int rows = matrix.GetLength(0); if (rows == 0) return false ; int columns = matrix.GetLength(1); // map for storing the index of combination of 2 1's Dictionary< int , HashSet< int > > table = new Dictionary< int , HashSet< int > >(); // 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 if (table.ContainsKey(j) && table[j].Contains(k)) { return true ; } if (table.ContainsKey(k) && table[k].Contains(j)) { return true ; } // store the indexes in hashset if (!table.ContainsKey(j)) { HashSet< int > x = new HashSet< int >(); x.Add(k); table.Add(j, x); } else { table[j].Add(k); } if (!table.ContainsKey(k)) { HashSet< int > x = new HashSet< int >(); x.Add(j); table.Add(k, x); } else { table[k].Add(j); } } } } } 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)) Console.Write( "Yes" ); else Console.Write( "No" ); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // An efficient approach based Javascript program to // find if there is a rectangle with 1 as // corners. // Returns true if there is a rectangle with // 1 as corners. function isRectangle(matrix) { // finding row and column size let rows = matrix.length; if (rows == 0) return false ; let columns = matrix[0].length; // map for storing the index of // combination of 2 1's let table = new Map(); // scanning from top to bottom line by line for (let i = 0; i < rows; i++) { for (let j = 0; j < columns - 1; j++) { for (let 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 if (table.has(j) && table.get(j).has(k)) { return true ; } if (table.has(k) && table.get(k).has(j)) { return true ; } // store the indexes in hashset if (!table.has(j)) { let x = new Set(); x.add(k); table.set(j, x); } else { table.get(j).add(k); } if (!table.has(k)) { let x = new Set(); x.add(j); table.set(k, x); } else { table.get(k).add(j); } } } } } return false ; } let mat = [[ 1, 0, 0, 1, 0 ], [ 0, 0, 1, 0, 1 ], [ 0, 0, 0, 1, 0 ], [ 1, 0, 1, 0, 1 ]]; if (isRectangle(mat)) document.write( "Yes" ); else document.write( "No" ); // This code is contributed by unknown2108 </script> |
输出
Yes
时间复杂性： O（n*m） 2. )
更有效的方法
前一种方法扫描每对列索引，以找到2个1的每个组合。
- 要更有效地找到2 1的每个组合，请将每一行转换为一组列索引。
- 然后，从行集合中选择列索引对，以快速获得2个1的每个组合。
- 如果一对列索引多次出现，则有一个角为1的矩形。
- 运行时变成O（m*n+n*n*log（n*n））。这是因为矩阵中有m*n个单元格，最多有O（n^2）个列索引组合，我们使用的是一个映射，它将在log（n）time中存储每个条目。
- 此外，如果n>m，则通过首先转置矩阵，运行时变为O（m*n+m*m*log（m*m））。
注意，min{m*n+n*n*log（n*n），m*n+m*m*log（m*m）}是O（m*n+p*p*log（p*p）），p=max（n，m）。
以下是上述方法的实施情况：
C++
// C++ implementation comes from: // Written by Niteesh Kumar and Michael Wehar // References: // [1] F. Mráz, D. Prusa, and M. Wehar. // Two-dimensional Pattern Matching against // Basic Picture Languages. CIAA 2019. // [2] D. Prusa and M. Wehar. Complexity of // Searching for 2 by 2 Submatrices in Boolean // Matrices. DLT 2020. #include <bits/stdc++.h> using namespace std; bool searchForRectangle( int rows, int cols, vector<vector< int >> mat) { // Make sure that matrix is non-trivial if (rows < 2 || cols < 2) { return false ; } // Create map int num_of_keys; map< int , vector< int >> adjsList; if (rows >= cols) { // Row-wise num_of_keys = rows; // Convert each row into vector of col indexes for ( int i = 0; i < rows; i++) { for ( int j = 0; j < cols; j++) { if (mat[i][j]) { adjsList[i].push_back(j); } } } } else { // Col-wise num_of_keys = cols; // Convert each col into vector of row indexes for ( int i = 0; i < rows; i++) { for ( int j = 0; j < cols; j++) { if (mat[i][j]) { adjsList[j].push_back(i); } } } } // Search for a rectangle whose four corners are 1's map<pair< int , int >, int > pairs; for ( int i = 0; i < num_of_keys; i++) { vector< int > values = adjsList[i]; int size = values.size(); for ( int j = 0; j < size - 1; j++) { for ( int k = j + 1; k < size; k++) { pair< int , int > temp = make_pair(values[j], values[k]); if (pairs.find(temp) != pairs.end()) { return true ; } else { pairs[temp] = i; } } } } 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 (searchForRectangle(4, 5, mat)) cout << "Yes" ; else cout << "No" ; } |
输出
Yes
时间复杂性： O（m*n+p*p*log（p*p）），p=max（n，m）。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
