Dada una array N * M mat[][] que consta de caracteres en minúsculas, la tarea es encontrar el costo mínimo para llegar desde la celda mat[0][0] a la celda mat[N-1][M-1 ] . Si está en una celda mat[i][j] , puede saltar a las celdas mat[i+1][j] , mat[i][j+1] , mat[i-1][j] , mat[i][j-1] (sin salirse de los límites) con un coste de 1 . Además, puede saltar a cualquier celda mat[m][n] tal que mat[n][m] = mat[i][j] con un costo de 0 .
Ejemplos:
Entrada: mat[][] = {“abc”, “efg”, “hij”}
Salida: 4
Una de las rutas más cortas será:
{0, 0} -> {0, 1} -> {0, 2 } -> {1, 2} -> {2, 2}
Todas las aristas tienen un peso de 1, por lo que la respuesta es 4.
Entrada: mat[][] = {“abc”, “efg”, “hbj” }
Salida: 2
{0, 0} -> {0, 1} -> {2, 1} -> {2, 2}
1 + 0 + 1 = 2
Enfoque ingenuo: un enfoque para resolver este problema será 0-1 BFS . Visualice la configuración como un gráfico con N * M Nodes. Todos los Nodes estarán conectados a Nodes adyacentes con arista de peso 1 y los Nodes con los mismos caracteres con arista de peso 0 . Ahora, BFS se puede usar para encontrar la ruta más corta desde el tapete de celdas [0][0] hasta el tapete de celdas [N-1][M-1]. La complejidad temporal de esto será O((N * M) 2 ) porque el número de aristas será del orden O((N * M) 2 ).
Enfoque eficiente: para cada carácter X, busque todos los caracteres a los que se encuentra adyacente. Ahora, cree un gráfico con una cantidad de Nodes como la cantidad de caracteres distintos en la string, cada uno de los cuales representa un carácter.
Cada Node X tendrá un borde de peso 1 con todos los Nodes representando los caracteres adyacentes al carácter X en el gráfico real. Luego, se puede ejecutar un BFS desde el Node que representa mat[0][0] hasta el Node que representa mat[N-1][M-1] en este nuevo gráfico. La complejidad de tiempo de este enfoque será O(N * M) para preprocesar el gráfico y la complejidad de tiempo para ejecutar el BFS se puede considerar constante.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
const int MAX = 26;
// Function to return
// the value (x - 97)
int f(int x)
{
return x - 'a';
}
// Function to return the minimum cost
int findMinCost(vector<string> arr)
{
int n = arr.size();
int m = arr[0].size();
// Graph
vector<vector<int> > gr(MAX);
// Adjacency matrix
bool edge[MAX][MAX];
// Initialising the adjacency matrix
for (int k = 0; k < MAX; k++)
for (int l = 0; l < MAX; l++)
edge[k][l] = 0;
// Creating the adjacency matrix
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
if (i + 1 < n and !edge[f(arr[i][j])][f(arr[i + 1][j])]) {
gr[f(arr[i][j])].push_back(f(arr[i + 1][j]));
edge[f(arr[i][j])][f(arr[i + 1][j])] = 1;
}
if (j - 1 >= 0 and !edge[f(arr[i][j])][f(arr[i][j - 1])]) {
gr[f(arr[i][j])].push_back(f(arr[i][j - 1]));
edge[f(arr[i][j])][f(arr[i][j - 1])] = 1;
}
if (j + 1 < m and !edge[f(arr[i][j])][f(arr[i][j + 1])]) {
gr[f(arr[i][j])].push_back(f(arr[i][j + 1]));
edge[f(arr[i][j])][f(arr[i][j + 1])] = 1;
}
if (i - 1 >= 0 and !edge[f(arr[i][j])][f(arr[i - 1][j])]) {
gr[f(arr[i][j])].push_back(f(arr[i - 1][j]));
edge[f(arr[i][j])][f(arr[i - 1][j])] = 1;
}
}
// Queue to perform BFS
queue<int> q;
q.push(arr[0][0] - 'a');
// Visited array
bool v[MAX] = { 0 };
// To store the depth of BFS
int d = 0;
// BFS
while (q.size()) {
// Number of elements in
// the current level
int cnt = q.size();
// Inner loop
while (cnt--) {
// Current element
int curr = q.front();
// Popping queue
q.pop();
// If the current node has
// already been visited
if (v[curr])
continue;
v[curr] = 1;
// Checking if the current
// node is the required node
if (curr == arr[n - 1][m - 1] - 'a')
return d;
// Iterating through the current node
for (auto it : gr[curr])
q.push(it);
}
// Updating the depth
d++;
}
return -1;
}
// Driver code
int main()
{
vector<string> arr = { "abc",
"def",
"gbi" };
cout << findMinCost(arr);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
static int MAX = 26;
// Function to return
// the value (x - 97)
static int f(int x)
{
return x - 'a';
}
// Function to return the minimum cost
static int findMinCost(String[] arr)
{
int n = arr.length;
int m = arr[0].length();
// Graph
Vector<Integer>[] gr = new Vector[MAX];
for (int i = 0; i < MAX; i++)
gr[i] = new Vector<Integer>();
// Adjacency matrix
boolean[][] edge = new boolean[MAX][MAX];
// Initialising the adjacency matrix
for (int k = 0; k < MAX; k++)
for (int l = 0; l < MAX; l++)
edge[k][l] = false;
// Creating the adjacency matrix
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
if (i + 1 < n && !edge[f(arr[i].charAt(j))][f(arr[i + 1].charAt(j))])
{
gr[f(arr[i].charAt(j))].add(f(arr[i + 1].charAt(j)));
edge[f(arr[i].charAt(j))][f(arr[i + 1].charAt(j))] = true;
}
if (j - 1 >= 0 && !edge[f(arr[i].charAt(j))][f(arr[i].charAt(j - 1))])
{
gr[f(arr[i].charAt(j))].add(f(arr[i].charAt(j - 1)));
edge[f(arr[i].charAt(j))][f(arr[i].charAt(j - 1))] = true;
}
if (j + 1 < m && !edge[f(arr[i].charAt(j))][f(arr[i].charAt(j + 1))])
{
gr[f(arr[i].charAt(j))].add(f(arr[i].charAt(j + 1)));
edge[f(arr[i].charAt(j))][f(arr[i].charAt(j + 1))] = true;
}
if (i - 1 >= 0 && !edge[f(arr[i].charAt(j))][f(arr[i - 1].charAt(j))])
{
gr[f(arr[i].charAt(j))].add(f(arr[i - 1].charAt(j)));
edge[f(arr[i].charAt(j))][f(arr[i - 1].charAt(j))] = true;
}
}
// Queue to perform BFS
Queue<Integer> q = new LinkedList<Integer>();
q.add(arr[0].charAt(0) - 'a');
// Visited array
boolean[] v = new boolean[MAX];
// To store the depth of BFS
int d = 0;
// BFS
while (q.size() > 0)
{
// Number of elements in
// the current level
int cnt = q.size();
// Inner loop
while (cnt-- > 0)
{
// Current element
int curr = q.peek();
// Popping queue
q.remove();
// If the current node has
// already been visited
if (v[curr])
continue;
v[curr] = true;
// Checking if the current
// node is the required node
if (curr == arr[n - 1].charAt(m - 1) - 'a')
return d;
// Iterating through the current node
for (Integer it : gr[curr])
q.add(it);
}
// Updating the depth
d++;
}
return -1;
}
// Driver code
public static void main(String[] args)
{
String[] arr = { "abc", "def", "gbi" };
System.out.print(findMinCost(arr));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation of the approach
MAX = 26
# Function to return
# the value (x - 97)
def f(x):
return ord(x) - ord('a')
# Function to return the minimum cost
def findMinCost( arr):
global MAX
n = len(arr)
m = len(arr[0])
# Graph
gr = []
for x in range(MAX):
gr.append([])
# Adjacency matrix
edge = []
# Initialising the adjacency matrix
for k in range(MAX):
edge.append([])
for l in range(MAX):
edge[k].append(0)
# Creating the adjacency matrix
for i in range(n):
for j in range(m):
if (i + 1 < n and edge[f(arr[i][j])][f(arr[i + 1][j])] == 0):
gr[f(arr[i][j])].append(f(arr[i + 1][j]))
edge[f(arr[i][j])][f(arr[i + 1][j])] = 1
if (j - 1 >= 0 and edge[f(arr[i][j])][f(arr[i][j - 1])] == 0):
gr[f(arr[i][j])].append(f(arr[i][j - 1]))
edge[f(arr[i][j])][f(arr[i][j - 1])] = 1
if (j + 1 < m and edge[f(arr[i][j])][f(arr[i][j + 1])] == 0):
gr[f(arr[i][j])].append(f(arr[i][j + 1]))
edge[f(arr[i][j])][f(arr[i][j + 1])] = 1
if (i - 1 >= 0 and edge[f(arr[i][j])][f(arr[i - 1][j])] == 0):
gr[f(arr[i][j])].append(f(arr[i - 1][j]))
edge[f(arr[i][j])][f(arr[i - 1][j])] = 1
# Queue to perform BFS
q = []
q.append(ord(arr[0][0]) - ord('a'))
# Visited array
v = []
for i in range(MAX):
v.append(0)
# To store the depth of BFS
d = 0
# BFS
while (len(q) > 0):
# Number of elements in
# the current level
cnt = len(q)
# Inner loop
while (cnt > 0):
cnt = cnt - 1
# Current element
curr = q[0]
# Popping queue
q.pop(0)
# If the current node has
# already been visited
if (v[curr] != 0):
continue
v[curr] = 1
# Checking if the current
# node is the required node
if (curr == (ord(arr[n - 1][m - 1]) - ord('a'))):
return d
# Iterating through the current node
for it in gr[curr]:
q.append(it)
# Updating the depth
d = d + 1
return -1
# Driver code
arr =[ "abc","def","gbi" ]
print( findMinCost(arr))
# This code is contributed by Arnab Kundu
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
static int MAX = 26;
// Function to return
// the value (x - 97)
static int f(int x)
{
return x - 'a';
}
// Function to return the minimum cost
static int findMinCost(String[] arr)
{
int n = arr.Length;
int m = arr[0].Length;
// Graph
List<int>[] gr = new List<int>[MAX];
for (int i = 0; i < MAX; i++)
gr[i] = new List<int>();
// Adjacency matrix
bool[,] edge = new bool[MAX, MAX];
// Initialising the adjacency matrix
for (int k = 0; k < MAX; k++)
for (int l = 0; l < MAX; l++)
edge[k,l] = false;
// Creating the adjacency matrix
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
if (i + 1 < n && !edge[f(arr[i][j]),f(arr[i + 1][j])])
{
gr[f(arr[i][j])].Add(f(arr[i + 1][j]));
edge[f(arr[i][j]), f(arr[i + 1][j])] = true;
}
if (j - 1 >= 0 && !edge[f(arr[i][j]),f(arr[i][j - 1])])
{
gr[f(arr[i][j])].Add(f(arr[i][j - 1]));
edge[f(arr[i][j]), f(arr[i][j - 1])] = true;
}
if (j + 1 < m && !edge[f(arr[i][j]),f(arr[i][j + 1])])
{
gr[f(arr[i][j])].Add(f(arr[i][j + 1]));
edge[f(arr[i][j]), f(arr[i][j + 1])] = true;
}
if (i - 1 >= 0 && !edge[f(arr[i][j]),f(arr[i - 1][j])])
{
gr[f(arr[i][j])].Add(f(arr[i - 1][j]));
edge[f(arr[i][j]), f(arr[i - 1][j])] = true;
}
}
// Queue to perform BFS
Queue<int> q = new Queue<int>();
q.Enqueue(arr[0][0] - 'a');
// Visited array
bool[] v = new bool[MAX];
// To store the depth of BFS
int d = 0;
// BFS
while (q.Count > 0)
{
// Number of elements in
// the current level
int cnt = q.Count;
// Inner loop
while (cnt-- > 0)
{
// Current element
int curr = q.Peek();
// Popping queue
q.Dequeue();
// If the current node has
// already been visited
if (v[curr])
continue;
v[curr] = true;
// Checking if the current
// node is the required node
if (curr == arr[n - 1][m - 1] - 'a')
return d;
// Iterating through the current node
foreach (int it in gr[curr])
q.Enqueue(it);
}
// Updating the depth
d++;
}
return -1;
}
// Driver code
public static void Main(String[] args)
{
String[] arr = { "abc", "def", "gbi" };
Console.Write(findMinCost(arr));
}
}
// This code is contributed by 29AjayKumar
2
Complejidad de Tiempo : O(N * M).
Espacio Auxiliar : O(N * M).
Publicación traducida automáticamente
Artículo escrito por DivyanshuShekhar1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA