Dada una array mat[][] de tamaño N×N donde dos elementos de la array son ‘1’ que denota la coordenada del rectángulo y ‘0’ denota el espacio vacío, la tarea es encontrar las otras dos coordenadas del rectángulo .
Nota : puede haber múltiples respuestas posibles para este problema, imprima cualquiera de ellas.
Ejemplos:
Entrada: mat[][] = {{0, 0, 1, 0}, {0, 0, 1, 0}, {0, 0, 0, 0}, {0, 0, 0, 0 }}
Salida : {{0, 0, 1, 1}, {0, 0, 1, 1}, {0, 0, 0, 0}, {0, 0, 0, 0}}
Explicación:
0 0 1 1
0 0 1 1
0 0 0 0
0 0 0 0
Las coordenadas {{0, 2}, {0, 3}, {1, 2}, {1, 3}} forman el rectánguloEntrada: mat[][] = {{0, 0, 1, 0}, {0, 0, 0, 0}, {1, 0, 0, 0}, {0, 0, 0, 0}}
Salida : {{1, 0, 1, 0}, {0, 0, 0, 0}, {1, 0, 1, 0}, {0, 0, 0, 0}}
Enfoque: la coordenada restante se puede encontrar usando estas coordenadas dadas porque algunos puntos pueden tener una fila común y algunos pueden tener una columna común. Siga los pasos a continuación para resolver el problema:
- Inicialice dos pares, digamos p1 y p2 para almacenar la posición de 1 en la array inicial mat[].
- Inicialice dos pares, digamos p3 y p4 para almacenar la posición donde se insertará el nuevo 1 para convertirlo en un rectángulo.
- Recorra la array usando dos bucles anidados y encuentre los pares p1 y p2 .
- Ahora hay tres casos posibles:
- Si p1.primero y p2.primero son iguales, en este caso sumando 1 a p1.primero y p2.primero nos da p3.primero y p4.primero mientras que p3.segundo y p4.segundo siguen siendo los mismos que p1.segundo y p2. segundo respectivamente.
- Si p1.segundo y p2.segundo son iguales, en este caso sumando 1 a p1.segundo y p2.segundo obtenemos p3.segundo y p4.segundo , mientras que p3.primero y p4.primero siguen siendo los mismos que p1.primero y p2.primero.
- Si ninguna de las coordenadas es igual, entonces p3.primero = p2.primero , p3.segundo = p1.segundo , p4.primero = p1.primero y p4.segundo = p2.segundo .
- Reemplace las coordenadas de p3 y p4 con 1 e imprima la array.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the remaining
// two rectangle coordinates
void Create_Rectangle(vector<string> arr, int n)
{
// Pairs to store the position of given
// two coordinates of the rectangle.
pair<int, int> p1 = { -1, -1 };
pair<int, int> p2 = { -1, -1 };
// Pairs to store the remaining two
// coordinates of the rectangle.
pair<int, int> p3;
pair<int, int> p4;
// Traverse through matrix and
// find pairs p1 and p2
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (arr[i][j] == '1')
if (p1.first == -1)
p1 = { i, j };
else
p2 = { i, j };
}
}
p3 = p1;
p4 = p2;
// First Case
if (p1.first == p2.first) {
p3.first = (p1.first + 1) % n;
p4.first = (p2.first + 1) % n;
}
// Second Case
else if (p1.second == p2.second) {
p3.second = (p1.second + 1) % n;
p4.second = (p2.second + 1) % n;
}
// Third Case
else {
swap(p3.first, p4.first);
}
arr[p3.first][p3.second] = '1';
arr[p4.first][p4.second] = '1';
// Print the matrix
for (int i = 0; i < n; i++) {
cout << arr[i] << endl;
}
}
// Driver code
int main()
{
// Given Input
int n = 4;
vector<string> arr{ "0010", "0000", "1000", "0000" };
// Function Call
Create_Rectangle(arr, n);
return 0;
}
Java
// Java program for above approach
import java.awt.*;
import java.util.*;
class GFG{
static class pair<T, V>{
T first;
V second;
}
// Function to find the remaining
// two rectangle coordinates
static void Create_Rectangle(ArrayList<String> arr, int n)
{
// Pairs to store the position of given
// two coordinates of the rectangle.
pair<Integer, Integer> p1 = new pair<>();
p1.first = -1;
p1.second= -1;
pair<Integer, Integer> p2 = new pair<>();
p2.first = -1;
p2.second = -1;
// Pairs to store the remaining two
// coordinates of the rectangle.
pair<Integer,Integer> p3 = new pair<>();
pair<Integer, Integer> p4 = new pair<>();
// Traverse through matrix and
// find pairs p1 and p2
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (arr.get(i).charAt(j) == '1')
if (p1.first == -1) {
p1.first =i;
p1.second = j;
}
else {
p2.first = i;
p2.second = j;
}
}
}
p3 = p1;
p4 = p2;
// First Case
if (p1.first.intValue() == (p2.first).intValue()) {
p3.first = (p1.first + 1) % n;
p4.first = (p2.first + 1) % n;
}
// Second Case
else if (p1.second.intValue()==(p2.second).intValue()) {
p3.second = (p1.second + 1) % n;
p4.second = (p2.second + 1) % n;
}
// Third Case
else {
int temp = p3.first;
p3.first = p4.first;
p4.first = temp;
}
// Print the matrix
for (int i = 0; i < n; i++) {
if(i==p3.first){
for (int j = 0;j<n;j++){
if(j==p3.second)
System.out.print('1');
else
System.out.print(arr.get(i).charAt(j));
}
}
else if(i==p4.first){
for (int j = 0;j<n;j++){
if(j==p4.second)
System.out.print('1');
else
System.out.print(arr.get(i).charAt(j));
}
}
else
System.out.print(arr.get(i));
System.out.println();
}
}
// Driver Code
public static void main(String[] args)
{
// Given Input
int n = 4;
ArrayList<String> arr = new ArrayList<>();
arr.add("0010");
arr.add("0000");
arr.add("1000");
arr.add("0000");
//{ , "0000", "1000", "0000" };
// Function Call
Create_Rectangle(arr, n);
}
}
// This code is contributed by hritikrommie.
Python3
# Python program for the above approach
# Function to find the remaining
# two rectangle coordinates
def Create_Rectangle(arr, n):
for i in range(n):
arr[i] = [i for i in arr[i]]
# Pairs to store the position of given
# two coordinates of the rectangle.
p1 = [-1, -1]
p2 = [-1, -1]
# Pairs to store the remaining two
# coordinates of the rectangle.
p3 = []
p4 = []
# Traverse through matrix and
# find pairs p1 and p2
for i in range(n):
for j in range(n):
if (arr[i][j] == '1'):
if (p1[0] == -1):
p1 = [i, j]
else:
p2 = [i, j]
p3 = p1
p4 = p2
# First Case
if (p1[0] == p2[0]):
p3[0] = (p1[0] + 1) % n
p4[0] = (p2[0] + 1) % n
# Second Case
elif (p1[1] == p2[1]):
p3[1] = (p1[1] + 1) % n
p4[1] = (p2[1] + 1) % n
# Third Case
else:
p3[0], p4[0] = p4[0],p3[0]
arr[p3[0]][p3[1]] = '1'
arr[p4[0]][p4[1]] = '1'
# Print the matrix
for i in range(n):
print("".join(arr[i]))
# Driver code
if __name__ == '__main__':
# Given Input
n = 4
arr = ["0010", "0000", "1000", "0000"]
# Function Call
Create_Rectangle(arr, n)
# This code is contributed by mohit kumar 29.
Javascript
<script>
// JavaScript program for the above approach
// Function to find the remaining
// two rectangle coordinates
function Create_Rectangle(arr, n) {
for (let i = 0; i < n; i++) {
arr[i] = arr[i].split("")
}
// Pairs to store the position of given
// two coordinates of the rectangle.
let p1 = [-1, -1];
let p2 = [-1, -1];
// Pairs to store the remaining two
// coordinates of the rectangle.
let p3 = [];
let p4 = [];
// Traverse through matrix and
// find pairs p1 and p2
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (arr[i][j] == '1')
if (p1[0] == -1)
p1 = [i, j];
else
p2 = [i, j];
}
}
p3 = p1;
p4 = p2;
// First Case
if (p1[0] == p2[0]) {
p3[0] = (p1[0] + 1) % n;
p4[0] = (p2[0] + 1) % n;
}
// Second Case
else if (p1[1] == p2[1]) {
p3[1] = (p1[1] + 1) % n;
p4[1] = (p2[1] + 1) % n;
}
// Third Case
else {
let temp = p3[0];
p3[0] = p4[0];
p4[0] = temp;
}
arr[p3[0]][p3[1]] = '1';
arr[p4[0]][p4[1]] = '1';
// Print the matrix
for (let i = 0; i < n; i++) {
document.write(arr[i].join("") + "<br>");
}
}
// Driver code
// Given Input
let n = 4;
let arr = ["0010", "0000", "1000", "0000"];
// Function Call
Create_Rectangle(arr, n);
</script>
Producción
1010 0000 1010 0000
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por anushikasethh y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA