Dada una array binaria de tamaño NxN, donde 1 indica que el número i se puede convertir en j y 0 indica que no se puede convertir. También se dan dos números X(<N) e Y(<N), la tarea es encontrar el número mínimo de pasos requeridos para convertir el número X a Y. Si no es posible, imprima -1.
Ejemplos:
Input:
{{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
{ 0, 0, 0, 0, 1, 0, 0, 0, 0, 0}
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1}
{ 0, 0, 0, 1, 0, 0, 0, 0, 0, 0}
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
{ 0, 1, 0, 0, 0, 0, 0, 0, 0, 0}
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1}}
X = 2, Y = 3
Output: 2
Convert 2 -> 4 -> 3, which is the minimum way possible.
Input:
{{ 0, 0, 0, 0}
{ 0, 0, 0, 1}
{ 0, 0, 0, 0}
{ 0, 1, 0, 0}}
X = 1, Y = 2
Output: -1
Enfoque: este problema es una variante del algoritmo de Floyd-warshall donde hay un borde de peso 1 entre i y j ie mat[i][j]==1 , de lo contrario no tienen un borde y podemos asignar bordes tan infinito como lo hacemos en Floyd-Warshall. Encuentre la array solución y devuelva dp[i][j] si no es infinita. Devuelve -1 si es infinito, lo que significa que no hay camino posible entre ellos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
#define INF 99999
#define size 10
int findMinimumSteps(int mat[size][size], int x, int y, int n)
{
// dist[][] will be the output matrix that
// will finally have the shortest
// distances between every pair of numbers
int dist[n][n], i, j, k;
// Initially same as mat
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (mat[i][j] == 0)
dist[i][j] = INF;
else
dist[i][j] = 1;
if (i == j)
dist[i][j] = 1;
}
}
// Add all numbers one by one to the set
// of intermediate numbers. Before start of
// an iteration, we have shortest distances
// between all pairs of numbers such that the
// shortest distances consider only the numbers
// in set {0, 1, 2, .. k-1} as intermediate numbers.
// After the end of an iteration, vertex no. k is
// added to the set of intermediate numbers and
// the set becomes {0, 1, 2, .. k}
for (k = 0; k < n; k++) {
// Pick all numbers as source one by one
for (i = 0; i < n; i++) {
// Pick all numbers as destination for the
// above picked source
for (j = 0; j < n; j++) {
// If number k is on the shortest path from
// i to j, then update the value of dist[i][j]
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
// If no path
if (dist[x][y] < INF)
return dist[x][y];
else
return -1;
}
// Driver Code
int main()
{
int mat[size][size] = { { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
{ 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 1, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 } };
int x = 2, y = 3;
cout << findMinimumSteps(mat, x, y, size);
}
Java
// Java implementation of the above approach
class GFG
{
static int INF=99999;
static int findMinimumSteps(int mat[][], int x, int y, int n)
{
// dist[][] will be the output matrix that
// will finally have the shortest
// distances between every pair of numbers
int i, j, k;
int [][] dist= new int[n][n];
// Initially same as mat
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (mat[i][j] == 0)
dist[i][j] = INF;
else
dist[i][j] = 1;
if (i == j)
dist[i][j] = 1;
}
}
// Add all numbers one by one to the set
// of intermediate numbers. Before start of
// an iteration, we have shortest distances
// between all pairs of numbers such that the
// shortest distances consider only the numbers
// in set {0, 1, 2, .. k-1} as intermediate numbers.
// After the end of an iteration, vertex no. k is
// added to the set of intermediate numbers and
// the set becomes {0, 1, 2, .. k}
for (k = 0; k < n; k++) {
// Pick all numbers as source one by one
for (i = 0; i < n; i++) {
// Pick all numbers as destination for the
// above picked source
for (j = 0; j < n; j++) {
// If number k is on the shortest path from
// i to j, then update the value of dist[i][j]
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
// If no path
if (dist[x][y] < INF)
return dist[x][y];
else
return -1;
}
// Driver Code
public static void main(String []args)
{
int [][] mat = { { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
{ 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 1, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 } };
int x = 2, y = 3;
int size=mat.length;
System.out.println( findMinimumSteps(mat, x, y, size));
}
}
// This code is contributed by ihritik
Python3
# Python3 implementation of the above approach
INF = 99999
size = 10
def findMinimumSteps(mat, x, y, n):
# dist[][] will be the output matrix
# that will finally have the shortest
# distances between every pair of numbers
dist = [[0 for i in range(n)]
for i in range(n)]
i, j, k = 0, 0, 0
# Initially same as mat
for i in range(n):
for j in range(n):
if (mat[i][j] == 0):
dist[i][j] = INF
else:
dist[i][j] = 1
if (i == j):
dist[i][j] = 1
# Add all numbers one by one to the set
# of intermediate numbers. Before start
# of an iteration, we have shortest distances
# between all pairs of numbers such that the
# shortest distances consider only the numbers
# in set {0, 1, 2, .. k-1} as intermediate
# numbers. After the end of an iteration, vertex
# no. k is added to the set of intermediate
# numbers and the set becomes {0, 1, 2, .. k}
for k in range(n):
# Pick all numbers as source one by one
for i in range(n):
# Pick all numbers as destination
# for the above picked source
for j in range(n):
# If number k is on the shortest path from
# i to j, then update the value of dist[i][j]
if (dist[i][k] + dist[k][j] < dist[i][j]):
dist[i][j] = dist[i][k] + dist[k][j]
# If no path
if (dist[x][y] < INF):
return dist[x][y]
else:
return -1
# Driver Code
mat = [[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 ],
[ 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 1, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 ]]
x, y = 2, 3
print(findMinimumSteps(mat, x, y, size))
# This code is contributed by Mohit kumar 29
C#
// C# implementation of the above approach
using System;
class GFG
{
static int INF=99999;
static int findMinimumSteps(int [,]mat, int x, int y, int n)
{
// dist[][] will be the output matrix that
// will finally have the shortest
// distances between every pair of numbers
int i, j, k;
int [,] dist= new int[n,n];
// Initially same as mat
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (mat[i,j] == 0)
dist[i,j] = INF;
else
dist[i,j] = 1;
if (i == j)
dist[i,j] = 1;
}
}
// Add all numbers one by one to the set
// of intermediate numbers. Before start of
// an iteration, we have shortest distances
// between all pairs of numbers such that the
// shortest distances consider only the numbers
// in set {0, 1, 2, .. k-1} as intermediate numbers.
// After the end of an iteration, vertex no. k is
// added to the set of intermediate numbers and
// the set becomes {0, 1, 2, .. k}
for (k = 0; k < n; k++) {
// Pick all numbers as source one by one
for (i = 0; i < n; i++) {
// Pick all numbers as destination for the
// above picked source
for (j = 0; j < n; j++) {
// If number k is on the shortest path from
// i to j, then update the value of dist[i][j]
if (dist[i,k] + dist[k,j] < dist[i,j])
dist[i,j] = dist[i,k] + dist[k,j];
}
}
}
// If no path
if (dist[x,y] < INF)
return dist[x,y];
else
return -1;
}
// Driver Code
public static void Main()
{
int [,] mat = { { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
{ 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 1, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 } };
int x = 2, y = 3;
int size = mat.GetLength(0) ;
Console.WriteLine( findMinimumSteps(mat, x, y, size));
}
// This code is contributed by Ryuga
}
Javascript
<script>
// JavaScript implementation of the above approach
var INF=99999;
function findMinimumSteps(mat , x , y , n)
{
// dist will be the output matrix that
// will finally have the shortest
// distances between every pair of numbers
var i, j, k;
var dist= Array(n).fill().map(()=>Array(n).fill(0));
// Initially same as mat
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (mat[i][j] == 0)
dist[i][j] = INF;
else
dist[i][j] = 1;
if (i == j)
dist[i][j] = 1;
}
}
// Add all numbers one by one to the set
// of intermediate numbers. Before start of
// an iteration, we have shortest distances
// between all pairs of numbers such that the
// shortest distances consider only the numbers
// in set {0, 1, 2, .. k-1} as intermediate numbers.
// After the end of an iteration, vertex no. k is
// added to the set of intermediate numbers and
// the set becomes {0, 1, 2, .. k}
for (k = 0; k < n; k++) {
// Pick all numbers as source one by one
for (i = 0; i < n; i++) {
// Pick all numbers as destination for the
// above picked source
for (j = 0; j < n; j++) {
// If number k is on the
// shortest path from
// i to j, then update the
// value of dist[i][j]
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
// If no path
if (dist[x][y] < INF)
return dist[x][y];
else
return -1;
}
// Driver Code
var mat = [[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 ],
[ 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 1, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 ] ];
var x = 2, y = 3;
var size=mat.length;
document.write( findMinimumSteps(mat, x, y, size));
// This code contributed by Rajput-Ji
</script>
Producción:
2
Complejidad de tiempo: O(N 3 ), ya que estamos usando bucles anidados para atravesar N 3 veces.
Espacio auxiliar: O(N 2 ), ya que estamos usando espacio extra para la array dist .