Dada una array binaria arr[][] que tiene N filas y M columnas, la tarea es calcular el número mínimo de operaciones requeridas para establecer el valor de la coordenada (x, y) como 1 donde cada operación, seleccione cualquier índice tal que su valor es 1 y establece todos sus elementos de fila o columnas en 1 .
Ejemplo:
Entrada: arr[][] = {{0, 1, 0, 0}, {1, 1, 1, 0}, {0, 0, 1, 1}}, X = 1, Y = 3 Salida
: 1
Explicación: En la primera operación, seleccione la coordenada (2, 3) como arr[2][3] = 1, y establezca todo el valor en esa columna como 1. Por lo tanto, haciendo el valor de arr[1][3] = 1, en 1 operación que es la mínima posible.Entrada: arr[][] = {{0, 0}, {0, 0}}, X = 1, Y = 1
Salida: -1
Explicación: No es posible configurar el valor de la coordenada arr[1] [1] como 1 usando cualquier número de operaciones.
Enfoque: El problema dado es un problema basado en la implementación y se puede dividir en los siguientes casos:
- Caso 1 donde arr[x][y] ya es 1 . En tales casos, se requerirán 0 operaciones.
- Caso 2 donde cualquiera de la fila x o la columna y contiene un índice con valor 1. En tales casos, se requerirá 1 operación.
- Caso 3 donde existe al menos un bloque tal que arr[i][j] = 1 . En tales casos, se requerirán 2 movimientos.
- Caso 4 donde no existe bloque con valor 1 . En tales casos, es imposible realizar la tarea dada.
Por lo tanto, verifique para cada uno de los casos mencionados en el orden respectivo que le dará la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find minimum operations
// required to set the value of the given
// coordinates as 1 in matrix arr[][]
int minOperations(
vector<vector<int> > arr,
int x, int y)
{
// Case 1 where arr[x][y] = 1
if (arr[x][y]) {
// Return Answer
return 0;
}
// Loop to iterate a row
for (int i = 0; i < arr[0].size(); i++) {
// Case 2 for Xth row
if (arr[x][i])
return 1;
}
// Loop to iterate a column
for (int j = 0; j < arr.size(); j++) {
// Case 2 for Yth column
if (arr[j][y])
return 1;
}
// Loop to traverse arr[][]
for (int i = 0; i < arr.size(); i++) {
for (int j = 0; j < arr[0].size(); j++) {
// Case 3 where any
// arr[i][j] = 1
if (arr[i][j])
return 1;
}
}
// Case 4
return -1;
}
// Driver Code
int main()
{
vector<vector<int> > arr{ { 0, 1, 0, 0 },
{ 1, 1, 1, 0 },
{ 0, 0, 1, 1 } };
int x = 1;
int y = 3;
cout << minOperations(arr, x, y);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG {
// Function to find minimum operations
// required to set the value of the given
// coordinates as 1 in matrix arr[][]
static int minOperations(
int[][] arr,
int x, int y)
{
// Case 1 where arr[x][y] = 1
if (arr[x][y] > 0) {
// Return Answer
return 0;
}
// Loop to iterate a row
for (int i = 0; i < arr[0].length; i++) {
// Case 2 for Xth row
if (arr[x][i] > 0)
return 1;
}
// Loop to iterate a column
for (int j = 0; j < arr.length; j++) {
// Case 2 for Yth column
if (arr[j][y] > 0)
return 1;
}
// Loop to traverse arr[][]
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[0].length; j++) {
// Case 3 where any
// arr[i][j] = 1
if (arr[i][j] > 0)
return 1;
}
}
// Case 4
return -1;
}
// Driver Code
public static void main (String[] args) {
int[][] arr = { { 0, 1, 0, 0 },
{ 1, 1, 1, 0 },
{ 0, 0, 1, 1 } };
int x = 1;
int y = 3;
System.out.println(minOperations(arr, x, y));
}
}
// This code is contributed by hrithikgarg03188.
Python3
# Python program of the above approach # Function to find minimum operations # required to set the value of the given # coordinates as 1 in matrix arr[][] def minOperations(arr, x, y): # Case 1 where arr[x][y] = 1 if (arr[x][y]): # Return Answer return 0 # Loop to iterate a row for i in range(0, len(arr[0])): # Case 2 for Xth row if (arr[x][i]): return 1 # Loop to iterate a column for j in range(0, len(arr)): # Case 2 for Yth column if (arr[j][y]): return 1 # Loop to traverse arr[][] for i in range(0, len(arr)): for j in range(0, len(arr[0])): # Case 3 where any # arr[i][j] = 1 if (arr[i][j]): return 1 # Case 4 return -1 # Driver Code arr = [[0, 1, 0, 0], [1, 1, 1, 0], [0, 0, 1, 1]] x = 1 y = 3 print(minOperations(arr, x, y)) # This code is contributed by Taranpreet
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG {
// Function to find minimum operations
// required to set the value of the given
// coordinates as 1 in matrix [,]arr
static int minOperations(
int[,] arr,
int x, int y)
{
// Case 1 where arr[x,y] = 1
if (arr[x, y] > 0)
{
// Return Answer
return 0;
}
// Loop to iterate a row
for (int i = 0; i < arr.GetLength(0); i++) {
// Case 2 for Xth row
if (arr[x,i] > 0)
return 1;
}
// Loop to iterate a column
for (int j = 0; j < arr.Length; j++) {
// Case 2 for Yth column
if (arr[j,y] > 0)
return 1;
}
// Loop to traverse [,]arr
for (int i = 0; i < arr.GetLength(0); i++) {
for (int j = 0; j < arr.GetLength(1); j++) {
// Case 3 where any
// arr[i,j] = 1
if (arr[i,j] > 0)
return 1;
}
}
// Case 4
return -1;
}
// Driver Code
public static void Main(String[] args) {
int[,] arr = { { 0, 1, 0, 0 },
{ 1, 1, 1, 0 },
{ 0, 0, 1, 1 } };
int x = 1;
int y = 3;
Console.WriteLine(minOperations(arr, x, y));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript code for the above approach
// Function to find minimum operations
// required to set the value of the given
// coordinates as 1 in matrix arr[][]
function minOperations(arr, x, y)
{
// Case 1 where arr[x][y] = 1
if (arr[x][y])
{
// Return Answer
return 0;
}
// Loop to iterate a row
for (let i = 0; i < arr[0].length; i++) {
// Case 2 for Xth row
if (arr[x][i])
return 1;
}
// Loop to iterate a column
for (let j = 0; j < arr.length; j++) {
// Case 2 for Yth column
if (arr[j][y])
return 1;
}
// Loop to traverse arr[][]
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr[0].length; j++) {
// Case 3 where any
// arr[i][j] = 1
if (arr[i][j])
return 1;
}
}
// Case 4
return -1;
}
// Driver Code
let arr = [[0, 1, 0, 0],
[1, 1, 1, 0],
[0, 0, 1, 1]];
let x = 1;
let y = 3;
document.write(minOperations(arr, x, y));
// This code is contributed by Potta Lokesh
</script>
Producción
1
Complejidad temporal: O(N*M)
Espacio auxiliar: O(1)