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