Dada una array arr[] de tamaño N donde cada elemento es del rango [0, 9] . La tarea es llegar al último índice de la array a partir del primer índice. Desde el i -ésimo índice podemos pasar a (i – 1) th , (i + 1) th oa cualquier j -ésimo índice donde j ≠ i y arr[j] = arr[i] .
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4, 1, 5}
Salida: 2
Primero muévase del índice 0 al índice 4 y
luego del índice 4 al 5 .Entrada: arr[] = {1, 2, 3, 4, 5, 1}
Salida: 1
Enfoque: construya el gráfico a partir de la array dada donde el número de Nodes en el gráfico será igual al tamaño de la array. Cada Node del grafo i estará conectado al (i 1) th Node, (i + 1) th node y un Node j tal que i ≠ j y arr[i] = arr[j] . Ahora, la respuesta serán los bordes mínimos en el camino del índice 0 al índice N – 1 en el gráfico construido.
El gráfico para la array arr[] = {1, 2, 3, 4, 1, 5} se muestra en la siguiente imagen:
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define N 100005
vector<int> gr[N];
// Function to add edge
void add_edge(int u, int v)
{
gr[u].push_back(v);
gr[v].push_back(u);
}
// Function to return the minimum path
// from 0th node to the (n - 1)th node
int dijkstra(int n)
{
// To check whether an edge is visited or not
// and to keep distance of vertex from 0th index
int vis[n] = { 0 }, dist[n];
for (int i = 0; i < n; i++)
dist[i] = INT_MAX;
// Make 0th index visited and distance is zero
vis[0] = 1;
dist[0] = 0;
// Take a queue and push first element
queue<int> q;
q.push(0);
// Continue this until all vertices are visited
while (!q.empty()) {
int x = q.front();
// Remove the first element
q.pop();
for (int i = 0; i < gr[x].size(); i++) {
// Check if a vertex is already visited or not
if (vis[gr[x][i]] == 1)
continue;
// Make vertex visited
vis[gr[x][i]] = 1;
// Store the number of moves to reach element
dist[gr[x][i]] = dist[x] + 1;
// Push the current vertex into the queue
q.push(gr[x][i]);
}
}
// Return the minimum number of
// moves to reach (n - 1)th index
return dist[n - 1];
}
// Function to return the minimum number of moves
// required to reach the end of the array
int Min_Moves(int a[], int n)
{
// To store the positions of each element
vector<int> fre[10];
for (int i = 0; i < n; i++) {
if (i != n - 1)
add_edge(i, i + 1);
fre[a[i]].push_back(i);
}
// Add edge between same elements
for (int i = 0; i < 10; i++) {
for (int j = 0; j < fre[i].size(); j++) {
for (int k = j + 1; k < fre[i].size(); k++) {
if (fre[i][j] + 1 != fre[i][k]
and fre[i][j] - 1 != fre[i][k]) {
add_edge(fre[i][j], fre[i][k]);
}
}
}
}
// Return the required minimum number of moves
return dijkstra(n);
}
// Driver code
int main()
{
int a[] = { 1, 2, 3, 4, 1, 5 };
int n = sizeof(a) / sizeof(a[0]);
cout << Min_Moves(a, n);
return 0;
}
Java
// Java implementation of the approach
import java.io.*;
import java.util.*;
class GFG{
static ArrayList<
ArrayList<Integer>> gr = new ArrayList<
ArrayList<Integer>>();
static int N = 100005;
// Function to add edge
static void add_edge(int u, int v)
{
for(int i = 0; i < N; i++)
{
gr.add(new ArrayList<Integer>());
}
gr.get(u).add(v);
gr.get(v).add(u);
}
// Function to return the minimum path
// from 0th node to the (n - 1)th node
static int dijkstra(int n)
{
// To check whether an edge is visited
// or not and to keep distance of
// vertex from 0th index
int[] vis = new int[n];
Arrays.fill(vis, 0);
int[] dist = new int[n];
for(int i = 0; i < n; i++)
{
dist[i] = Integer.MAX_VALUE;
}
// Make 0th index visited and
// distance is zero
vis[0] = 1;
dist[0] = 0;
// Take a queue and push first element
Queue<Integer> q = new LinkedList<>();
q.add(0);
// Continue this until all vertices
// are visited
while (q.size() > 0)
{
// Remove the first element
int x = q.poll();
for(int i = 0; i < gr.get(x).size(); i++)
{
// Check if a vertex is already
// visited or not
if (vis[gr.get(x).get(i)] == 1)
{
continue;
}
// Make vertex visited
vis[gr.get(x).get(i)] = 1;
// Store the number of moves to
// reach element
dist[gr.get(x).get(i)] = dist[x] + 1;
// Push the current vertex into
// the queue
q.add(gr.get(x).get(i));
}
}
// Return the minimum number of
// moves to reach (n - 1)th index
return dist[n - 1];
}
// Function to return the minimum number of moves
// required to reach the end of the array
static int Min_Moves(int[] a, int n)
{
// To store the positions of each element
ArrayList<
ArrayList<Integer>> fre = new ArrayList<
ArrayList<Integer>>();
for(int i = 0; i < 10; i++)
{
fre.add(new ArrayList<Integer>());
}
for(int i = 0; i < n; i++)
{
if (i != n - 1)
{
add_edge(i, i + 1);
}
fre.get(a[i]).add(i);
}
// Add edge between same elements
for(int i = 0; i < 10; i++)
{
for(int j = 0;
j < fre.get(i).size();
j++)
{
for(int k = j + 1;
k < fre.get(i).size();
k++)
{
if (fre.get(i).get(j) + 1 !=
fre.get(i).get(k) &&
fre.get(i).get(j) - 1 !=
fre.get(i).get(k))
{
add_edge(fre.get(i).get(j),
fre.get(i).get(k));
}
}
}
}
// Return the required minimum
// number of moves
return dijkstra(n);
}
// Driver code
public static void main(String[] args)
{
int[] a = { 1, 2, 3, 4, 1, 5 };
int n = a.length;
System.out.println(Min_Moves(a, n));
}
}
// This code is contributed by avanitrachhadiya2155
Python3
# Python3 implementation of the approach from collections import deque N = 100005 gr = [[] for i in range(N)] # Function to add edge def add_edge(u, v): gr[u].append(v) gr[v].append(u) # Function to return the minimum path # from 0th node to the (n - 1)th node def dijkstra(n): # To check whether an edge is visited # or not and to keep distance of vertex # from 0th index vis = [0 for i in range(n)] dist = [10**9 for i in range(n)] # Make 0th index visited and # distance is zero vis[0] = 1 dist[0] = 0 # Take a queue and # append first element q = deque() q.append(0) # Continue this until # all vertices are visited while (len(q) > 0): x = q.popleft() # Remove the first element for i in gr[x]: # Check if a vertex is # already visited or not if (vis[i] == 1): continue # Make vertex visited vis[i] = 1 # Store the number of moves # to reach element dist[i] = dist[x] + 1 # Push the current vertex # into the queue q.append(i) # Return the minimum number of # moves to reach (n - 1)th index return dist[n - 1] # Function to return the minimum number of moves # required to reach the end of the array def Min_Moves(a, n): # To store the positions of each element fre = [[] for i in range(10)] for i in range(n): if (i != n - 1): add_edge(i, i + 1) fre[a[i]].append(i) # Add edge between same elements for i in range(10): for j in range(len(fre[i])): for k in range(j + 1,len(fre[i])): if (fre[i][j] + 1 != fre[i][k] and fre[i][j] - 1 != fre[i][k]): add_edge(fre[i][j], fre[i][k]) # Return the required # minimum number of moves return dijkstra(n) # Driver code a = [1, 2, 3, 4, 1, 5] n = len(a) print(Min_Moves(a, n)) # This code is contributed by Mohit Kumar
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
static List<List<int>> gr = new List<List<int>>();
static int N = 100005;
// Function to add edge
static void add_edge(int u, int v)
{
for(int i = 0; i < N; i++)
{
gr.Add(new List<int>());
}
gr[u].Add(v);
gr[v].Add(u);
}
// Function to return the minimum path
// from 0th node to the (n - 1)th node
static int dijkstra(int n)
{
// To check whether an edge is visited
// or not and to keep distance of
// vertex from 0th index
int[] vis = new int[n];
Array.Fill(vis, 0);
int[] dist = new int[n];
for(int i = 0; i < n; i++)
{
dist[i] = Int32.MaxValue;
}
// Make 0th index visited and
// distance is zero
vis[0] = 1;
dist[0] = 0;
// Take a queue and push first element
Queue<int> q = new Queue<int>();
q.Enqueue(0);
// Continue this until all vertices
// are visited
while(q.Count > 0)
{
// Remove the first element
int x = q.Dequeue();
for(int i = 0; i < gr[x].Count; i++ )
{
// Check if a vertex is already
// visited or not
if(vis[gr[x][i]] == 1)
{
continue;
}
// Make vertex visited
vis[gr[x][i]] = 1;
// Store the number of moves to
// reach element
dist[gr[x][i]] = dist[x] + 1;
// Push the current vertex into
// the queue
q.Enqueue(gr[x][i]);
}
}
// Return the minimum number of
// moves to reach (n - 1)th index
return dist[n - 1];
}
// Function to return the minimum number of moves
// required to reach the end of the array
static int Min_Moves(int[] a, int n)
{
// To store the positions of each element
List<List<int>> fre = new List<List<int>>();
for(int i = 0; i < 10; i++)
{
fre.Add(new List<int>());
}
for(int i = 0; i < n; i++)
{
if (i != n - 1)
{
add_edge(i, i + 1);
}
fre[a[i]].Add(i);
}
// Add edge between same elements
for(int i = 0; i < 10; i++)
{
for(int j = 0; j < fre[i].Count; j++)
{
for(int k = j + 1; k < fre[i].Count; k++)
{
if(fre[i][j] + 1 != fre[i][k] &&
fre[i][j] - 1 != fre[i][k])
{
add_edge(fre[i][j], fre[i][k]);
}
}
}
}
// Return the required minimum
// number of moves
return dijkstra(n);
}
// Driver code
static public void Main ()
{
int[] a = { 1, 2, 3, 4, 1, 5 };
int n = a.Length;
Console.WriteLine(Min_Moves(a, n));
}
}
// This code is contributed by rag2127
Javascript
<script>
// Javascript implementation of the approach
let gr = [];
let N = 100005;
// Function to add edge
function add_edge(u,v)
{
for(let i = 0; i < N; i++)
{
gr.push([]);
}
gr[u].push(v);
gr[v].push(u);
}
// Function to return the minimum path
// from 0th node to the (n - 1)th node
function dijkstra(n)
{
// To check whether an edge is visited
// or not and to keep distance of
// vertex from 0th index
let vis = new Array(n);
for(let i = 0; i < vis.length; i++)
{
vis[i] = 0;
}
let dist = new Array(n);
for(let i = 0; i < n; i++)
{
dist[i] = Number.MAX_VALUE;
}
// Make 0th index visited and
// distance is zero
vis[0] = 1;
dist[0] = 0;
// Take a queue and push first element
let q = [];
q.push(0);
// Continue this until all vertices
// are visited
while (q.length > 0)
{
// Remove the first element
let x = q.shift();
for(let i = 0; i < gr[x].length; i++)
{
// Check if a vertex is already
// visited or not
if (vis[gr[x][i]] == 1)
{
continue;
}
// Make vertex visited
vis[gr[x][i]] = 1;
// Store the number of moves to
// reach element
dist[gr[x][i]] = dist[x] + 1;
// Push the current vertex into
// the queue
q.push(gr[x][i]);
}
}
// Return the minimum number of
// moves to reach (n - 1)th index
return dist[n - 1];
}
// Function to return the minimum number of moves
// required to reach the end of the array
function Min_Moves(a,n)
{
// To store the positions of each element
let fre = [];
for(let i = 0; i < 10; i++)
{
fre.push([]);
}
for(let i = 0; i < n; i++)
{
if (i != n - 1)
{
add_edge(i, i + 1);
}
fre[a[i]].push(i);
}
// Add edge between same elements
for(let i = 0; i < 10; i++)
{
for(let j = 0;
j < fre[i].length;
j++)
{
for(let k = j + 1;
k < fre[i].length;
k++)
{
if (fre[i][j] + 1 !=
fre[i][k] &&
fre[i][j] - 1 !=
fre[i][k])
{
add_edge(fre[i][j],
fre[i][k]);
}
}
}
}
// Return the required minimum
// number of moves
return dijkstra(n);
}
// Driver code
let a = [1, 2, 3, 4, 1, 5 ];
let n = a.length;
document.write(Min_Moves(a, n));
// This code is contributed by unknown2108
</script>
Producción:
2
Complejidad temporal: O(n 2 )
Espacio Auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA