Hay una array binaria dada, necesitamos encontrar si existe algún rectángulo o cuadrado en la array dada cuyas cuatro esquinas son iguales a
Ejemplos:
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>
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>
C++
// C++ implementation comes from: // https://github.com/MichaelWehar/FourCornersProblem // 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"; }
Publicación traducida automáticamente
Artículo escrito por niteesh_Kr y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA