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: Sí
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>
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