Movimientos mínimos necesarios para cambiar de posición con la operación dada

Dados dos enteros S y T y un arreglo arr que contiene elementos del 1 al N sin ordenar. La tarea es encontrar el número mínimo de movimientos para mover el elemento Sth al lugar Tth en la array con la siguiente operación: 
Un solo movimiento consiste en lo siguiente 
 

// Initially b[] = {1, 2, 3, ..., N}
// arr[] is input array
for (i = 1..n)
   temp[arr[i]] = b[i]
b = temp

Si no es posible, imprima -1 en su lugar.
Ejemplos: 
 

Entrada: S = 2, T = 1, arr[] = {2, 3, 4, 1} 
Salida:
N es 4 (tamaño de arr[]) 
Mover 1: b[] = {4, 1, 2, 3} 
Movimiento 2: b[] = {3, 4, 1, 2} 
Movimiento 3: b[] = {2, 3, 4, 1}
Entrada: S = 3, T = 4, arr[] = {1 , 2, 3, 4} 
Salida: -1 
N es 4 (Tamaño de arr[]) 
Independientemente de cuántos movimientos se realicen, la permutación seguirá siendo la misma. 
 

Enfoque: la observación importante aquí es que solo nos preocupa la posición de un solo elemento, y no la array completa. Entonces, en cada movimiento, movemos el elemento en la posición S a la posición arr[S] , hasta llegar a la posición  T.
Dado que hay como máximo N lugares distintos a los que podemos llegar, si no llegamos a T en N movimientos, significaría que nunca podremos alcanzarlo.
A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the number of moves
int minimumMoves(int n, int a[], int s, int t)
{
    int i, x;
    x = s;
    for (i = 1; i <= n; i++) {
        if (x == t)
            break;
        x = a[x];
    }
 
    // Destination reached
    if (x == t)
        return i - 1;
    else
        return -1;
}
 
// Driver Code
int main()
{
    int s = 2, t = 1, i;
    int a[] = {-1, 2, 3, 4, 1};
    int n = sizeof(a) / sizeof(a[0]);
    cout << minimumMoves(n, a, s, t);
}

Java

// Java implementation of the approach
public class GFG{
 
// Function to return the number of moves
static int minimumMoves(int n, int a[], int s, int t)
{
    int i, x;
    x = s;
    for (i = 1; i <= n; i++) {
        if (x == t)
            break;
        x = a[x];
    }
 
    // Destination reached
    if (x == t)
        return i - 1;
    else
        return -1;
}
 
    // Driver Code
    public static void main(String []args){
    int s = 2, t = 1, i;
    int a[] = {-1, 2, 3, 4, 1};
    int n = a.length ;
    System.out.println(minimumMoves(n, a, s, t)); 
    }
    // This code is contributed by Ryuga
}

Python3

# Python3 implementation of the approach
 
# Function to return the number of moves
def minimumMoves(n, a, s, t):
 
    x = s
    for i in range(1, n+1): 
        # Destination reached
        if x == t:
            return i-1
        x = a[x]
      
    return -1
   
# Driver Code
if __name__ == "__main__":
 
    s, t = 2, 1
    a = [-1, 2, 3, 4, 1]
    n = len(a)
    print(minimumMoves(n, a, s, t))
  
# This code is contributed by Rituraj Jain

C#

// C# implementation of the approach
using System;
public class GFG{
 
// Function to return the number of moves
static int minimumMoves(int n, int []a, int s, int t)
{
    int i, x;
    x = s;
    for (i = 1; i <= n; i++) {
        if (x == t)
            break;
        x = a[x];
    }
 
    // Destination reached
    if (x == t)
        return i - 1;
    else
        return -1;
}
 
    // Driver Code
    public static void Main(){
    int s = 2, t = 1;
    int []a = {-1, 2, 3, 4, 1};
    int n = a.Length ;
    Console.WriteLine(minimumMoves(n, a, s, t));
    }
    // This code is contributed by inder_verma.
}

PHP

<?php
// PHP implementation of the approach
 
 
// Function to return the number of moves
function minimumMoves($n, $a, $s, $t)
{
    $i; $x;
    $x = $s;
    for ($i = 1; $i <= $n; $i++) {
        if ($x == $t)
            break;
        $x = $a[$x];
    }
 
    // Destination reached
    if ($x == $t)
        return $i - 1;
    else
        return -1;
}
 
// Driver Code
 
    $s = 2; $t = 1; $i;
    $a = array(-1, 2, 3, 4, 1);
    $n = count($a);
    echo minimumMoves($n, $a, $s, $t);
     // This code is contributed by inder_verma.
?>

Javascript

<script>
    // Javascript implementation of the approach  
     
    // Function to return the number of moves
    function minimumMoves(n, a, s, t)
    {
        let i, x;
        x = s;
        for (i = 1; i <= n; i++) {
            if (x == t)
                break;
            x = a[x];
        }
 
        // Destination reached
        if (x == t)
            return i - 1;
        else
            return -1;
    }
     
    let s = 2, t = 1;
    let a = [-1, 2, 3, 4, 1];
    let n = a.length ;
    document.write(minimumMoves(n, a, s, t));
      
     // This code is contributed by suresh07.
</script>
Producción: 

3

 

Publicación traducida automáticamente

Artículo escrito por Abdullah Aslam y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *