Dada una array binaria mat[][] de dimensiones N*M , la tarea es encontrar el número mínimo de vueltas requeridas de la array binaria dada de modo que no exista ningún camino desde la celda superior izquierda hasta la inferior. celda derecha que consta de solo 0s .
Ejemplos:
Entrada: mat[][] = {{0, 1, 0, 0}, {0, 1, 0, 0}, {0, 1, 0, 0}, {0, 0, 0, 0}}
Salida : 1
Explicación:
Operación 1: Voltear la celda en (1, 0) modifica la array dada a:
0 1 0 0
1 1 0 0
0 1 0 0
0 0 0 0
Después de las operaciones anteriores, no existe ninguna ruta desde la celda superior izquierda (0, 0) hasta la celda inferior derecha (3, 3) que consta de solo 0. Por lo tanto, el número total de lanzamientos requeridos es 1.Entrada: mat[][] = {{0, 0, 0, 0}, {0, 0, 0, 0}}
Salida: 2
Enfoque: el problema dado se puede resolver usando el DFS Traversal en la array dada y en base a la observación de que solo existen como máximo 2 cambios de Nodes, de modo que no existe ninguna ruta desde la celda superior izquierda hasta la inferior. celda derecha que consta de solo 0s . La idea es realizar el recorrido DFS desde la celda superior izquierda hasta la celda inferior derecha para cambiar como máximo una ruta e imprimir la cantidad de llamadas DFS exitosas como resultado. Siga los pasos a continuación para resolver el problema:
- Inicialice una función , digamos DFS(mat, i, j, N, M) que tome la celda actual, la array dada y su tamaño como parámetro y realice los siguientes pasos:
- Si la celda actual alcanza la celda (N – 1, M – 1) , devuelve true .
- Actualice el valor de la celda en (i, j) a 1 .
- Llame recursivamente a la función DFS en las cuatro direcciones de la celda actual, es decir, (i + 1, j) , (i, j + 1) , (i – 1, j) y (i, j – 1) si existe
- Si la llamada DFS de la celda (0, 0) devuelve false , entonces no existe tal ruta desde la celda superior izquierda a la inferior derecha que consta de 0s . Por lo tanto, imprima 0 como resultado y regrese de la función .
- Nuevamente, si la llamada DFS desde la celda (0, 0) devuelve false , entonces existe solo una ruta desde la celda superior izquierda a la inferior derecha que consta de 0s . Por lo tanto, imprima 1 como resultado y regrese de la función.
- De lo contrario, imprime 2 como resultado.
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;
// The four direction coordinates changes
// from the current cell
int direction[][2] = { { -1, 0 }, { 0, 1 },
{ 0, -1 }, { 1, 0 } };
// Function that returns true if there
// exists any path from the top-left to
// the bottom-right cell of 0s
bool dfs(vector<vector<int> >& matrix,
int i, int j, int N, int M)
{
// If the bottom-right cell is
// reached
if (i == N - 1 and j == M - 1) {
return true;
}
// Update the cell to 1
matrix[i][j] = 1;
// Traverse in all four directions
for (int k = 0; k < 4; k++) {
// Find the new coordinates
int newX = i + direction[k][0];
int newY = j + direction[k][1];
// If the new cell is valid
if (newX >= 0 and newX < N
and newY >= 0 and newY < M
and matrix[newX][newY] == 0) {
// Recursively call DFS
if (dfs(matrix, newX,
newY, N, M)) {
// If path exists, then
// return true
return true;
}
}
}
// Return false, if there doesn't
// exists any such path
return false;
}
// Function to flip the minimum number
// of cells such that there doesn't
// exists any such path from (0, 0) to
// (N - 1, M - 1) cell consisting of 0s
int solve(vector<vector<int> >& matrix)
{
int N = matrix.size();
int M = matrix[0].size();
// Case 1: If no such path exists
// already
if (!dfs(matrix, 0, 0, N, M)) {
return 0;
}
// Case 2: If there exists only
// one path
if (!dfs(matrix, 0, 0, N, M)) {
return 1;
}
// Case 3: If there exists two-path
return 2;
}
// Driver Code
int main()
{
vector<vector<int> > mat = {
{ 0, 1, 0, 0 },
{ 0, 1, 0, 0 },
{ 0, 0, 0, 0 }
};
cout << solve(mat);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG{
// The four direction coordinates changes
// from the current cell
static int[][] direction = { { -1, 0 }, { 0, 1 },
{ 0, -1 }, { 1, 0 } };
// Function that returns true if there
// exists any path from the top-left to
// the bottom-right cell of 0s
static boolean dfs(int matrix[][], int i, int j,
int N, int M)
{
// If the bottom-right cell is
// reached
if (i == N - 1 && j == M - 1)
{
return true;
}
// Update the cell to 1
matrix[i][j] = 1;
// Traverse in all four directions
for(int k = 0; k < 4; k++)
{
// Find the new coordinates
int newX = i + direction[k][0];
int newY = j + direction[k][1];
// If the new cell is valid
if (newX >= 0 && newX < N && newY >= 0 &&
newY < M && matrix[newX][newY] == 0)
{
// Recursively call DFS
if (dfs(matrix, newX, newY, N, M))
{
// If path exists, then
// return true
return true;
}
}
}
// Return false, if there doesn't
// exists any such path
return false;
}
// Function to flip the minimum number
// of cells such that there doesn't
// exists any such path from (0, 0) to
// (N - 1, M - 1) cell consisting of 0s
static int solve(int[][] matrix)
{
int N = matrix.length;
int M = matrix[0].length;
// Case 1: If no such path exists
// already
if (!dfs(matrix, 0, 0, N, M))
{
return 0;
}
// Case 2: If there exists only
// one path
if (!dfs(matrix, 0, 0, N, M))
{
return 1;
}
// Case 3: If there exists two-path
return 2;
}
// Driver code
public static void main(String[] args)
{
int[][] mat = { { 0, 1, 0, 0 },
{ 0, 1, 0, 0 },
{ 0, 0, 0, 0 } };
System.out.println(solve(mat));
}
}
// This code is contributed by MuskanKalra1
Python3
# Python3 program for the above approach # The four direction coordinates changes # from the current cell direction = [ [ -1, 0 ], [ 0, 1 ], [ 0, -1 ],[ 1, 0 ] ] # Function that returns true if there # exists any path from the top-left to # the bottom-right cell of 0s def dfs(i, j, N, M): global matrix # If the bottom-right cell is # reached if (i == N - 1 and j == M - 1): return True # Update the cell to 1 matrix[i][j] = 1 # Traverse in all four directions for k in range(4): # Find the new coordinates newX = i + direction[k][0] newY = j + direction[k][1] # If the new cell is valid if (newX >= 0 and newX < N and newY >= 0 and newY < M and matrix[newX][newY] == 0): # Recursively call DFS if (dfs(newX, newY, N, M)): # If path exists, then # return true return True # Return false, if there doesn't # exists any such path return False # Function to flip the minimum number # of cells such that there doesn't # exists any such path from (0, 0) to # (N - 1, M - 1) cell consisting of 0s def solve(): global matrix N = len(matrix) M = len(matrix[0]) # Case 1: If no such path exists # already if (not dfs(0, 0, N, M)): return 0 # Case 2: If there exists only # one path if (not dfs(0, 0, N, M)): return 1 # Case 3: If there exists two-path return 2 # Driver Code if __name__ == '__main__': matrix = [ [ 0, 1, 0, 0 ], [ 0, 1, 0, 0 ], [ 0, 0, 0, 0 ] ] print(solve()) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG{
// The four direction coordinates changes
// from the current cell
static int[,] direction = { { -1, 0 }, { 0, 1 },
{ 0, -1 }, { 1, 0 } };
// Function that returns true if there
// exists any path from the top-left to
// the bottom-right cell of 0s
static bool dfs(int [,]matrix, int i, int j,
int N, int M)
{
// If the bottom-right cell is
// reached
if (i == N - 1 && j == M - 1)
{
return true;
}
// Update the cell to 1
matrix[i, j] = 1;
// Traverse in all four directions
for(int k = 0; k < 4; k++)
{
// Find the new coordinates
int newX = i + direction[k, 0];
int newY = j + direction[k, 1];
// If the new cell is valid
if (newX >= 0 && newX < N && newY >= 0 &&
newY < M && matrix[newX, newY] == 0)
{
// Recursively call DFS
if (dfs(matrix, newX, newY, N, M))
{
// If path exists, then
// return true
return true;
}
}
}
// Return false, if there doesn't
// exists any such path
return false;
}
// Function to flip the minimum number
// of cells such that there doesn't
// exists any such path from (0, 0) to
// (N - 1, M - 1) cell consisting of 0s
static int solve(int[,] matrix)
{
int N = matrix.GetLength(0);
int M = matrix.GetLength(1);
// Case 1: If no such path exists
// already
if (!dfs(matrix, 0, 0, N, M))
{
return 0;
}
// Case 2: If there exists only
// one path
if (!dfs(matrix, 0, 0, N, M))
{
return 1;
}
// Case 3: If there exists two-path
return 2;
}
// Driver code
public static void Main(String[] args)
{
int[,] mat = { { 0, 1, 0, 0 },
{ 0, 1, 0, 0 },
{ 0, 0, 0, 0 } };
Console.WriteLine(solve(mat));
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// JavaScript program for the above approach
// The four direction coordinates changes
// from the current cell
let direction = [ [ -1, 0 ], [ 0, 1 ],
[ 0, -1 ], [ 1, 0 ] ];
// Function that returns true if there
// exists any path from the top-left to
// the bottom-right cell of 0s
function dfs(matrix, i, j, N, M)
{
// If the bottom-right cell is
// reached
if (i == N - 1 && j == M - 1) {
return true;
}
// Update the cell to 1
matrix[i][j] = 1;
// Traverse in all four directions
for (let k = 0; k < 4; k++) {
// Find the new coordinates
let newX = i + direction[k][0];
let newY = j + direction[k][1];
// If the new cell is valid
if (newX >= 0 && newX < N
&& newY >= 0 && newY < M
&& matrix[newX][newY] == 0) {
// Recursively call DFS
if (dfs(matrix, newX,
newY, N, M)) {
// If path exists, then
// return true
return true;
}
}
}
// Return false, if there doesn't
// exists any such path
return false;
}
// Function to flip the minimum number
// of cells such that there doesn't
// exists any such path from (0, 0) to
// (N - 1, M - 1) cell consisting of 0s
function solve(matrix)
{
let N = matrix.length;
let M = matrix[0].length;
// Case 1: If no such path exists
// already
if (!dfs(matrix, 0, 0, N, M)) {
return 0;
}
// Case 2: If there exists only
// one path
if (!dfs(matrix, 0, 0, N, M)) {
return 1;
}
// Case 3: If there exists two-path
return 2;
}
// Driver Code
let mat = [
[ 0, 1, 0, 0 ],
[ 0, 1, 0, 0 ],
[ 0, 0, 0, 0 ]
];
document.write(solve(mat));
</script>
Producción:
1
Complejidad de tiempo: O (N + M), ya que estamos usando bucles que atraviesan N y M veces (por separado).
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.
Publicación traducida automáticamente
Artículo escrito por kartikey134 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA