Dada una array commands[] , que consta de enteros con signo que indican la distancia y la dirección a recorrer junto con las coordenadas, y una array de obstáculos[] que indica las coordenadas a las que no se puede acceder, la tarea es encontrar el cuadrado del cuadrado de la distancia euclidiana máxima que se pueden recorrer partiendo del origen (0, 0) y mirando hacia el norte, siguiendo los comandos especificados en la secuencia como en el arreglo commands[] , de los siguientes tres tipos:
- -2 : Gire a la izquierda 90 grados.
- -1 : Gire a la derecha 90 grados.
- 1<= X <= 9 : Avanzar en X unidades.
Ejemplos:
Entrada: comandos[] = {4, -1, 4, -2, 4}, obstáculos[] = {{ 2, 4 }}
Salida: 65
Explicación:
Paso 1: (0, 0) -> (0, 4 )
Paso 2: (0, 4) -> (1, 4)
Paso 3 y 4:
Obstáculos
Paso 5: (1, 4) -> (1, 8)Entrada: comandos[] = {4, -1, 3}, obstáculos[] = {}
Salida: 25
Enfoque: siga los pasos a continuación para resolver el problema:
- Inicialmente, el robot está en (0, 0) mirando al norte.
- Asigne variables para realizar un seguimiento de la posición actual y la dirección del robot después de cada paso.
- Almacena las coordenadas de los obstáculos en un HashMap .
- Haga 2 arrays (dx[], dy[]) y almacene todos los movimientos posibles en coordenadas x e y de acuerdo con el cambio de dirección.
- Si se encuentra un cambio de dirección, cambie la dirección actual haciendo referencia a las 2 arrays.
- De lo contrario, sigue moviéndote en la misma dirección hasta que encuentres un cambio de dirección si no hay obstáculos en el medio.
- Finalmente, calcule el cuadrado de las coordenadas x e y.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include<bits/stdc++.h>
using namespace std;
void robotSim(vector<int> commands,
vector<pair<int, int>> obstacles)
{
// Possible movements in x coordinate.
vector<int> dx = { 0, 1, 0, -1 };
// Possible movements in y coordinate.
vector<int> dy = { 1, 0, -1, 0 };
int x = 0, y = 0;
int di = 0;
// Put all obstacles into hashmap.
map<pair<int, int>, int>obstacleSet;
for(auto i:obstacles)
obstacleSet[i] = 1;
// Maximum distance
int ans = 0;
// Iterate commands.
for(int cmd : commands)
{
// Left direction
if (cmd == -2)
di = (di-1) % 4;
// Right direction
else if (cmd == -1)
di = (di + 1) % 4;
// If no direction changes
else
{
for(int i = 0; i < cmd; i++)
{
// Checking for obstacles.
if (obstacleSet.find({x + dx[di],
y + dy[di]}) ==
obstacleSet.end())
{
// Update x coordinate
x += dx[di];
// Update y coordinate
y += dy[di];
// Updating for max distance
ans = max(ans, x * x + y * y);
}
}
}
}
cout << ans << endl;
}
// Driver Code
int main()
{
vector<int> commands = { 4, -1, 4, -2, 4 };
vector<pair<int, int>> obstacles = { { 2, 4 } };
robotSim(commands, obstacles);
}
// This code is contributed by grand_master
Java
// Java program to implement
// the above approach
import java.util.*;
import java.awt.Point;
class GFG{
static void robotSim(List<Integer> commands,
List<Point> obstacles)
{
// Possible movements in x coordinate.
List<Integer> dx = Arrays.asList(0, 1, 0, -1);
// Possible movements in y coordinate.
List<Integer> dy = Arrays.asList(1, 0, -1, 0);
int x = 0, y = 0;
int di = 0;
// Put all obstacles into hashmap.
HashMap<Point, Integer> obstacleSet = new HashMap<>();
for(Point i : obstacles)
obstacleSet.put(i, 1);
// Maximum distance
int ans = 0;
// Iterate commands.
for(Integer cmd : commands)
{
// Left direction
if (cmd == -2)
di = (di - 1) % 4;
// Right direction
else if (cmd == -1)
di = (di + 1) % 4;
// If no direction changes
else
{
for(int i = 0; i < cmd; i++)
{
// Checking for obstacles.
if (!obstacleSet.containsKey(
new Point(x + dx.get(di),
y + dy.get(di))))
{
// Update x coordinate
x += dx.get(di);
// Update y coordinate
y += dy.get(di);
// Updating for max distance
ans = Math.max(ans, x * x + y * y);
}
}
}
}
System.out.println(ans);
}
// Driver Code
public static void main(String[] args)
{
List<Integer> commands = Arrays.asList(
4, -1, 4, -2, 4);
List<Point> obstacles = new ArrayList<>();
obstacles.add(new Point(2, 4));
robotSim(commands, obstacles);
}
}
// This code is contributed by divyesh072019
Python3
# Python3 Program to implement # the above approach def robotSim(commands, obstacles): # Possible movements in x coordinate. dx = [0, 1, 0, -1] # Possible movements in y coordinate. dy = [1, 0, -1, 0] # Initialise position to (0, 0). x, y = 0, 0 # Initial direction is north. di = 0 # Put all obstacles into hashmap. obstacleSet = set(map(tuple, obstacles)) # maximum distance ans = 0 # Iterate commands. for cmd in commands: # Left direction if cmd == -2: di = (di-1) % 4 # Right direction elif cmd == -1: di = (di + 1) % 4 # If no direction changes else: for i in range(cmd): # Checking for obstacles. if (x + dx[di], y + dy[di]) \ not in obstacleSet: # Update x coordinate x += dx[di] # Update y coordinate y += dy[di] # Updating for max distance ans = max(ans, x * x + y * y) print(ans) # Driver Code if __name__ == "__main__": commands = [4, -1, 4, -2, 4] obstacles = [[2, 4]] robotSim(commands, obstacles)
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG {
static void robotSim(List<int> commands,
List<Tuple<int, int>> obstacles)
{
// Possible movements in x coordinate.
List<int> dx = new List<int>(new int[]{ 0, 1, 0, -1 });
// Possible movements in y coordinate.
List<int> dy = new List<int>(new int[]{ 1, 0, -1, 0 });
int x = 0, y = 0;
int di = 0;
// Put all obstacles into hashmap.
Dictionary<Tuple<int, int>, int> obstacleSet =
new Dictionary<Tuple<int, int>, int>();
foreach(Tuple<int, int> i in obstacles)
obstacleSet[i] = 1;
// Maximum distance
int ans = 0;
// Iterate commands.
foreach(int cmd in commands)
{
// Left direction
if (cmd == -2)
di = (di - 1) % 4;
// Right direction
else if (cmd == -1)
di = (di + 1) % 4;
// If no direction changes
else
{
for(int i = 0; i < cmd; i++)
{
// Checking for obstacles.
if (!obstacleSet.ContainsKey(new Tuple<int,int>(x + dx[di],
y + dy[di])))
{
// Update x coordinate
x += dx[di];
// Update y coordinate
y += dy[di];
// Updating for max distance
ans = Math.Max(ans, x * x + y * y);
}
}
}
}
Console.WriteLine(ans);
}
// Driver code
static void Main()
{
List<int> commands = new List<int>(new int[]{ 4, -1, 4, -2, 4 });
List<Tuple<int, int>> obstacles = new List<Tuple<int, int>>();
obstacles.Add(new Tuple<int, int>(2,4));
robotSim(commands, obstacles);
}
}
// This code is contributed by divyeshrabadiya07.
Javascript
// JavaScript program to implement
// the above approach
function robotSim(commands, obstacles)
{
// Possible movements in x coordinate.
let dx = [0, 1, 0, -1];
// Possible movements in y coordinate.
let dy = [1, 0, -1, 0];
let x = 0, y = 0;
let di = 0;
// Put all obstacles into hashmap.
let obstacleSet = new Map();
obstacles.forEach(i=>{
obstacleSet.set([i].join(), 1);
})
// Maximum distance
let ans = 0;
// Iterate commands.
for(let j = 0; j < commands.length; j++)
{
let cmd = commands[j];
// Left direction
if (cmd == -2)
di = (di-1) % 4;
// Right direction
else if (cmd == -1)
di = (di + 1) % 4;
// If no direction changes
else
{
for(let i = 0; i < cmd; i++)
{
// Checking for obstacles.
if (!obstacleSet.has([x + dx[di], y + dy[di]].join()))
{
// Update x coordinate
x = x + dx[di];
// Update y coordinate
y = y + dy[di];
// Updating for max distance
ans = Math.max(ans, x * x + y * y);
}
}
}
}
console.log(ans);
}
// Driver Code
let commands = [4, -1, 4, -2, 4];
let obstacles = [[2, 4]];
robotSim(commands, obstacles);
// This code is contributed by Gautam goel (gautamgoel962)
Producción:
65
Complejidad de Tiempo: O(N)
Espacio Auxiliar: O(N + M), donde M es la longitud de la array de obstáculos.
Publicación traducida automáticamente
Artículo escrito por vivekverma1719 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA