Compruebe si es posible viajar a todos los puntos en un tiempo dado moviéndose en cuatro direcciones adyacentes

Dadas 3 arrays X[], Y[] y T[], todas de tamaño N , donde X[i] e Y[i] representan la i-ésima coordenada y T[i] representa el tiempo en segundos. Encuentre que es posible llegar a todas las coordenadas (X[i], Y[i]) en el tiempo T[i] desde las coordenadas iniciales (0, 0) . El puntero se puede mover en cuatro direcciones ( x +1, y ), ( x − 1, y ), ( x, y + 1) y (x, y − 1). Pasar de una coordenada a otra toma 1 segundo y no puede quedarse en su propio palacio.

Ejemplos:

Entrada: N = 2, X[] = {1, 1},  
                      Y[] = {2, 1},  
                      T[] = {3, 6}
Salida:
Explicación: Supongamos una array 2D como esta:
 

En la array anterior, cada punto se define como coordenadas x e y Viaje desde ( 0, 0 ) -> ( 0, 1 ) -> ( 1, 1 ) -> ( 1, 2 ) en 3 segundos Luego desde ( 1, 2 ) -> ( 1, 1 ) -> ( 1, 0 ) -> ( 1, 1 ) en el sexto segundo. Entonces, sí, es posible alcanzar todas las coordenadas en un tiempo determinado.

Entrada: N = 1, X[] = {100 },  
                      Y[] = {100 },  
                      T[] = {2}
Salida: No
Explicación: No es posible alcanzar las coordenadas X e Y en 2 segundos desde las coordenadas ( 0, 0 ).

 

Planteamiento: La idea para resolver este problema se basa en que para pasar del i-ésimo punto al (i+1)-ésimo punto se necesita abs(X[i+1] – X[i]) + abs(Y [i+1] – Y[i]) tiempo. En el caso del primer punto, el punto anterior es (0, 0). Entonces, si este tiempo es menor que T[i] entonces está bien, de lo contrario, viola la condición. Siga los pasos a continuación para resolver el problema:

  • Haga tres variables currentX, currentY, currentTime e inicialice a cero .
  • Haga una variable booleana isPossible e inicialice en true .
  • Itere sobre el rango [0, N) usando la variable i y realice las siguientes tareas:
    • Si (abs(X[i] – currentX ) + abs( Y[i] – currentY )) es mayor que (T[i] – currentTime) , entonces haga que isPossible sea falso.
    • De lo contrario, si   ((abs(X[i] – currentX ) + abs( Y[i] – currentY )) % 2 no es igual a (T[i] – currentTime) % 2 , entonces haga que isPossible sea falso.
    • De lo contrario , cambie los valores anteriores de currentX, currentY y currentTime con Xi, Yi y Ti.
  • Después de realizar los pasos anteriores, devuelve el valor de isPossible como respuesta.

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;
 
// Function to check if it is possible
// to traverse all the points.
bool CheckItisPossible(int X[], int Y[],
                       int T[], int N)
{
 
    // Make 3 variables to store given
    // ith values
    int currentX = 0, currentY = 0,
        currentTime = 0;
 
    // Also, make a bool variable to
    // check it is possible
    bool IsPossible = true;
 
    // Now, iterate on all the coordinates
    for (int i = 0; i < N; i++) {
 
        // check first condition
        if ((abs(X[i] - currentX)
             + abs(Y[i] - currentY))
            > (T[i] - currentTime)) {
            // means thats not possible to
            // reach current coordinate
            // at Ithtime from previous coordinate
            IsPossible = false;
            break;
        }
        else if (((abs(X[i] - currentX)
                   + abs(Y[i] - currentY))
                  % 2)
                 > ((T[i] - currentTime) % 2)) {
            // means thats not possible to
            // reach current coordinate
            // at Ithtime from previous coordinate
            IsPossible = false;
            break;
        }
        else {
            // If both above conditions are false
            // then we change the values of current
            // coordinates
            currentX = X[i];
            currentY = Y[i];
            currentTime = T[i];
        }
    }
 
    return IsPossible;
}
 
// Driver Code
int main()
{
    int X[] = { 1, 1 };
    int Y[] = { 2, 1 };
    int T[] = { 3, 6 };
    int N = sizeof(X[0]) / sizeof(int);
    bool ans = CheckItisPossible(X, Y, T, N);
 
    if (ans == true) {
        cout << "Yes"
             << "\n";
    }
    else {
        cout << "No"
             << "\n";
    }
    return 0;
}

Java

// Java program for the above approach
public class GFG {
     
    // Function to check if it is possible
    // to traverse all the points.
    static boolean CheckItisPossible(int X[], int Y[],
                        int T[], int N)
    {
     
        // Make 3 variables to store given
        // ith values
        int currentX = 0, currentY = 0,
            currentTime = 0;
     
        // Also, make a bool variable to
        // check it is possible
        boolean IsPossible = true;
     
        // Now, iterate on all the coordinates
        for (int i = 0; i < N; i++) {
     
            // check first condition
            if ((Math.abs(X[i] - currentX) +
                 Math.abs(Y[i] - currentY)) > (T[i] - currentTime)) {
                 
                // means thats not possible to
                // reach current coordinate
                // at Ithtime from previous coordinate
                IsPossible = false;
                break;
            }
            else if (((Math.abs(X[i] - currentX) +
                       Math.abs(Y[i] - currentY)) % 2) > ((T[i] - currentTime) % 2)) {
                // means thats not possible to
                // reach current coordinate
                // at Ithtime from previous coordinate
                IsPossible = false;
                break;
            }
            else {
                // If both above conditions are false
                // then we change the values of current
                // coordinates
                currentX = X[i];
                currentY = Y[i];
                currentTime = T[i];
            }
        }
     
        return IsPossible;
    }
     
    // Driver Code
    public static void main(String[] args)
    {
        int X[] = { 1, 1 };
        int Y[] = { 2, 1 };
        int T[] = { 3, 6 };
        int N = X.length;
        boolean ans = CheckItisPossible(X, Y, T, N);
     
        if (ans == true) {
            System.out.println("Yes");
        }
        else {
            System.out.println("No");
        }
    }
}
 
// This code is contributed by AnkThon

Python3

# python program for the above approach
 
# Function to check if it is possible
# to traverse all the points.
def CheckItisPossible(X, Y, T, N):
 
        # Make 3 variables to store given
        # ith values
    currentX = 0
    currentY = 0
    currentTime = 0
 
    # Also, make a bool variable to
    # check it is possible
    IsPossible = True
 
    # Now, iterate on all the coordinates
    for i in range(0, N):
 
                # check first condition
        if ((abs(X[i] - currentX)
             + abs(Y[i] - currentY))
                > (T[i] - currentTime)):
             # means thats not possible to
             # reach current coordinate
             # at Ithtime from previous coordinate
            IsPossible = False
            break
 
        elif (((abs(X[i] - currentX)
                + abs(Y[i] - currentY))
               % 2)
              > ((T[i] - currentTime) % 2)):
            # means thats not possible to
            # reach current coordinate
            # at Ithtime from previous coordinate
            IsPossible = False
            break
 
        else:
           # If both above conditions are false
           # then we change the values of current
           # coordinates
            currentX = X[i]
            currentY = Y[i]
            currentTime = T[i]
 
    return IsPossible
 
# Driver Code
if __name__ == "__main__":
 
    X = [1, 1]
    Y = [2, 1]
    T = [3, 6]
    N = len(X)
    ans = CheckItisPossible(X, Y, T, N)
 
    if (ans == True):
        print("Yes")
    else:
        print("No")
 
    # This code is contributed by rakeshsahni

C#

// C# program for the above approach
using System;
 
class GFG {
     
    // Function to check if it is possible
    // to traverse all the points.
    static bool CheckItisPossible(int []X, int []Y,
                        int []T, int N)
    {
     
        // Make 3 variables to store given
        // ith values
        int currentX = 0, currentY = 0,
            currentTime = 0;
     
        // Also, make a bool variable to
        // check it is possible
        bool IsPossible = true;
     
        // Now, iterate on all the coordinates
        for (int i = 0; i < N; i++) {
     
            // check first condition
            if ((Math.Abs(X[i] - currentX) +
                 Math.Abs(Y[i] - currentY)) > (T[i] - currentTime)) {
                 
                // means thats not possible to
                // reach current coordinate
                // at Ithtime from previous coordinate
                IsPossible = false;
                break;
            }
            else if (((Math.Abs(X[i] - currentX) +
                       Math.Abs(Y[i] - currentY)) % 2) > ((T[i] - currentTime) % 2)) {
                // means thats not possible to
                // reach current coordinate
                // at Ithtime from previous coordinate
                IsPossible = false;
                break;
            }
            else {
                // If both above conditions are false
                // then we change the values of current
                // coordinates
                currentX = X[i];
                currentY = Y[i];
                currentTime = T[i];
            }
        }
     
        return IsPossible;
    }
     
    // Driver Code
    public static void Main()
    {
        int []X = { 1, 1 };
        int []Y = { 2, 1 };
        int []T = { 3, 6 };
        int N = X.Length;
        bool ans = CheckItisPossible(X, Y, T, N);
     
        if (ans == true) {
            Console.Write("Yes");
        }
        else {
            Console.Write("No");
        }
    }
}
 
// This code is contributed by Samim Hossain Mondal.

Javascript

<script>
// Javascript program for the above approach
 
// Function to check if it is possible
// to traverse all the points.
function CheckItisPossible(X, Y, T, N)
{
 
    // Make 3 variables to store given
    // ith values
    let currentX = 0, currentY = 0,
        currentTime = 0;
 
    // Also, make a bool variable to
    // check it is possible
    let IsPossible = true;
 
    // Now, iterate on all the coordinates
    for (let i = 0; i < N; i++) {
 
        // check first condition
        if ((Math.abs(X[i] - currentX)
             + Math.abs(Y[i] - currentY))
            > (T[i] - currentTime)) {
            // means thats not possible to
            // reach current coordinate
            // at Ithtime from previous coordinate
            IsPossible = false;
            break;
        }
        else if (((Math.abs(X[i] - currentX)
                   + Math.abs(Y[i] - currentY))
                  % 2)
                 > ((T[i] - currentTime) % 2)) {
            // means thats not possible to
            // reach current coordinate
            // at Ithtime from previous coordinate
            IsPossible = false;
            break;
        }
        else {
            // If both above conditions are false
            // then we change the values of current
            // coordinates
            currentX = X[i];
            currentY = Y[i];
            currentTime = T[i];
        }
    }
 
    return IsPossible;
}
 
// Driver Code
let X = [ 1, 1 ];
let Y = [ 2, 1 ];
let T = [ 3, 6 ];
let N = X.length;
let ans = CheckItisPossible(X, Y, T, N);
 
if (ans == true) {
    document.write("Yes" + "\n");
}
else {
    document.write("No" + "\n");
}
     
// This code is contributed by Samim Hossain Mondal.
</script>
Producción

Yes

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por hrithikgarg03188 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 *