Comprobar si es posible llegar a cualquier punto de la circunferencia de un círculo dado desde el origen

Dada una string S que representa una secuencia de movimientos ( L , R , U y D ) y un número entero R que representa el radio de un círculo cuyo centro es el origen (0, 0) , la tarea es comprobar si es posible llegar a cualquier punto de la circunferencia del círculo dado desde el origen eligiendo cualquier subsecuencia de movimientos de la cuerda S . Si es posible llegar a un punto en la circunferencia, escriba «Sí» . De lo contrario, escriba “No”
Las operaciones requeridas a realizar para cada dirección son las siguientes:

  • Si el carácter actual es L , disminuya la coordenada x en 1 .
  • Si el carácter actual es R , entonces incremente la coordenada x en 1 .
  • Si el carácter actual es U , entonces incremente la coordenada y en 1 .
  • Si el carácter actual es D , disminuya la coordenada y en 1 .

Ejemplos:

Entrada: S = “LLRULD”, R = 3
Salida: Si
Explicación: 
Seleccionando la subsecuencia “LLL”, el cambio de coordenadas al realizar la secuencia de movimientos son:
(0, 0) → (-1, 0) → (- 2, 0) → (-3, 0)
Dado que (-3, 0) se encuentra en la circunferencia del círculo dado, es posible llegar a la  

Entrada: S = “ULRDLD”, R = 6
Salida: No

Enfoque ingenuo: el enfoque más simple es generar todas las subsecuencias posibles de la string S dada y si existe alguna subsecuencia de movimientos que resulten en alcanzar la circunferencia del círculo desde el origen (0, 0) , imprima «Sí» . De lo contrario, escriba “No” .

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

Enfoque eficiente: el enfoque anterior se puede optimizar en función de las siguientes observaciones:

  • Dado que la ruta que debe considerarse comienza desde el origen (0, 0) , si el recuento máximo entre cada uno de los caracteres L , R , U y D en la string tiene un valor superior a R , entonces la ruta desde el origen hasta la circunferencia del círculo existe.
  • Si existen dos valores X e Y tales que la suma de los cuadrados de X e Y es R 2 , entonces existe un camino triangular desde el origen hasta la circunferencia del círculo.

Siga los pasos a continuación para resolver el problema dado:

  • Almacene el recuento de caracteres L , R , U y D , en la string S dada en una variable, digamos cntL , cntR , cntU y cntD respectivamente.
  • Si el máximo de cntL , cntR , cntU y cntD es al menos R , entonces existe una trayectoria en línea recta desde el origen hasta la circunferencia. Por lo tanto, imprima “Sí” .
  • Si el cuadrado del máximo de cntL y cntR y el máximo de cntU y cntD es al menos R 2 , imprima «Sí», ya que existe un camino triangular desde el origen hasta la circunferencia del círculo.
  • Si no se presenta ninguno de los casos anteriores, escriba “No” .

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 reach any point on circumference
// of the given circle from (0,0)
string isPossible(string S, int R, int N)
{
    // Stores the count of 'L', 'R'
    int cntl = 0, cntr = 0;
 
    // Stores the count of 'U', 'D'
    int cntu = 0, cntd = 0;
 
    // Traverse the string S
    for (int i = 0; i < N; i++) {
        // Update the count of L
        if (S[i] == 'L')
            cntl++;
 
        // Update the count of R
        else if (S[i] == 'R')
            cntr++;
 
        // Update the count of U
        else if (S[i] == 'U')
            cntu++;
 
        // Update the count of D
        else
            cntd++;
    }
 
    // Condition 1 for reaching
    // the circumference
    if (max(max(cntl, cntr), max(cntu, cntd)) >= R)
        return "Yes";
 
    unordered_map<int, int> mp;
 
    int r_square = R * R;
 
    for (int i = 1; i * i <= r_square; i++) {
 
        // Store the value
        // of (i * i) in the Map
        mp[i * i] = i;
 
        // Check if (r_square - i*i)
        // already present in HashMap
        if (mp.find(r_square - i * i) != mp.end()) {
           
            // If it is possible to reach the
            // point (± mp[r_square - i*i], ± i)
            if (max(cntl, cntr)
                >= mp[r_square - i * i]
                && max(cntu, cntd) >= i)
 
                return "Yes";
 
            // If it is possible to reach the
            // point (±i, ±mp[r_square-i*i])
            if (max(cntl, cntr) >= i
                && max(cntu, cntd)
                >= mp[r_square - i * i])
 
                return "Yes";
        }
    }
 
    // If it is impossible to reach
    return "No";
}
 
// Driver Code
int main()
{
    string S = "RDLLDDLDU";
    int R = 5;
    int N = S.length();
   
    cout << isPossible(S, R, N);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG{
 
// Function to check if it is possible
// to reach any point on circumference
// of the given circle from (0,0)
static String isPossible(String S, int R, int N)
{
     
    // Stores the count of 'L', 'R'
    int cntl = 0, cntr = 0;
 
    // Stores the count of 'U', 'D'
    int cntu = 0, cntd = 0;
 
    // Traverse the string S
    for(int i = 0; i < N; i++)
    {
         
        // Update the count of L
        if (S.charAt(i) == 'L')
            cntl++;
 
        // Update the count of R
        else if (S.charAt(i) == 'R')
            cntr++;
 
        // Update the count of U
        else if (S.charAt(i) == 'U')
            cntu++;
 
        // Update the count of D
        else
            cntd++;
    }
 
    // Condition 1 for reaching
    // the circumference
    if (Math.max(Math.max(cntl, cntr),
                 Math.max(cntu, cntd)) >= R)
        return "Yes";
 
    HashMap<Integer, Integer> mp = new HashMap<>();
 
    int r_square = R * R;
 
    for(int i = 1; i * i <= r_square; i++)
    {
         
        // Store the value
        // of (i * i) in the Map
        mp.put(i * i, i);
 
        // Check if (r_square - i*i)
        // already present in HashMap
        if (mp.containsKey(r_square - i * i))
        {
             
            // If it is possible to reach the
            // point (± mp[r_square - i*i], ± i)
            if (Math.max(cntl, cntr) >=
                mp.get(r_square - i * i) &&
                Math.max(cntu, cntd) >= i)
                return "Yes";
 
            // If it is possible to reach the
            // point (±i, ±mp[r_square-i*i])
            if (Math.max(cntl, cntr) >= i &&
                Math.max(cntu, cntd) >=
                mp.get(r_square - i * i))
                return "Yes";
        }
    }
 
    // If it is impossible to reach
    return "No";
}
 
// Driver Code
public static void main(String[] args)
{
    String S = "RDLLDDLDU";
    int R = 5;
    int N = S.length();
 
    System.out.println(isPossible(S, R, N));
}
}
 
// This code is contributed by Kingash

Python3

# Python3 program for the above approach
 
# Function to check if it is possible
# to reach any point on circumference
# of the given circle from (0,0)
def isPossible(S, R, N):
 
    # Stores the count of 'L', 'R'
    cntl = 0
    cntr = 0
 
    # Stores the count of 'U', 'D'
    cntu = 0
    cntd = 0
 
    # Traverse the string S
    for i in range(N):
         
        # Update the count of L
        if (S[i] == 'L'):
            cntl += 1
 
        # Update the count of R
        elif (S[i] == 'R'):
            cntr += 1
 
        # Update the count of U
        elif (S[i] == 'U'):
            cntu += 1
 
        # Update the count of D
        else:
            cntd += 1
 
    # Condition 1 for reaching
    # the circumference
    if (max(max(cntl, cntr), max(cntu, cntd)) >= R):
        return "Yes"
 
    mp = {}
 
    r_square = R * R
 
    i = 1
    while i * i <= r_square:
         
        # Store the value
        # of (i * i) in the Map
        mp[i * i] = i
 
        # Check if (r_square - i*i)
        # already present in HashMap
        if ((r_square - i * i) in mp):
 
            # If it is possible to reach the
            # point (± mp[r_square - i*i], ± i)
            if (max(cntl, cntr) >= mp[r_square - i * i] and
               max(cntu, cntd) >= i):
 
                return "Yes"
 
            # If it is possible to reach the
            # point (±i, ±mp[r_square-i*i])
            if (max(cntl, cntr) >= i and
               max(cntu, cntd) >= mp[r_square - i * i]):
 
                return "Yes"
 
        i += 1
 
    # If it is impossible to reach
    return "No"
 
# Driver Code
if __name__ == "__main__":
 
    S = "RDLLDDLDU"
    R = 5
    N = len(S)
 
    print(isPossible(S, R, N))
 
# This code is contributed by ukasp

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
public class GFG
{
 
  // Function to check if it is possible
  // to reach any point on circumference
  // of the given circle from (0,0)
  static string isPossible(string S, int R, int N)
  {
 
    // Stores the count of 'L', 'R'
    int cntl = 0, cntr = 0;
 
    // Stores the count of 'U', 'D'
    int cntu = 0, cntd = 0;
 
    // Traverse the string S
    for(int i = 0; i < N; i++)
    {
 
      // Update the count of L
      if (S[i] == 'L')
        cntl++;
 
      // Update the count of R
      else if (S[i] == 'R')
        cntr++;
 
      // Update the count of U
      else if (S[i] == 'U')
        cntu++;
 
      // Update the count of D
      else
        cntd++;
    }
 
    // Condition 1 for reaching
    // the circumference
    if (Math.Max(Math.Max(cntl, cntr),
                 Math.Max(cntu, cntd)) >= R)
      return "Yes";
 
    Dictionary<int, int> mp = new Dictionary<int, int>();
 
    int r_square = R * R;
 
    for(int i = 1; i * i <= r_square; i++)
    {
 
      // Store the value
      // of (i * i) in the Map
      mp.Add(i * i, i);
 
      // Check if (r_square - i*i)
      // already present in HashMap
      if (mp.ContainsKey(r_square - i * i))
      {
 
        // If it is possible to reach the
        // point (± mp[r_square - i*i], ± i)
        if (Math.Max(cntl, cntr) >=
            mp[r_square - i * i] &&
            Math.Max(cntu, cntd) >= i)
          return "Yes";
 
        // If it is possible to reach the
        // point (±i, ±mp[r_square-i*i])
        if (Math.Max(cntl, cntr) >= i &&
            Math.Max(cntu, cntd) >=
            mp[r_square - i * i])
          return "Yes";
      }
    }
 
    // If it is impossible to reach
    return "No";
  }
  static public void Main ()
  {
    string S = "RDLLDDLDU";
    int R = 5;
    int N = S.Length;
 
    Console.WriteLine(isPossible(S, R, N));
  }
}
 
// This code is contributed by offbeat

Javascript

<script>
 
// Javascript program for the above approach
 
// Function to check if it is possible
// to reach any point on circumference
// of the given circle from (0,0)
function isPossible(S, R, N)
{
    // Stores the count of 'L', 'R'
    var cntl = 0, cntr = 0;
 
    // Stores the count of 'U', 'D'
    var cntu = 0, cntd = 0;
 
    // Traverse the string S
    for (var i = 0; i < N; i++) {
        // Update the count of L
        if (S[i] == 'L')
            cntl++;
 
        // Update the count of R
        else if (S[i] == 'R')
            cntr++;
 
        // Update the count of U
        else if (S[i] == 'U')
            cntu++;
 
        // Update the count of D
        else
            cntd++;
    }
 
    // Condition 1 for reaching
    // the circumference
    if (Math.max(Math.max(cntl, cntr), Math.max(cntu, cntd)) >= R)
        return "Yes";
 
    var mp = new Map();
 
    var r_square = R * R;
 
    for (var i = 1; i * i <= r_square; i++) {
 
        // Store the value
        // of (i * i) in the Map
        mp.set(i * i, i);
 
        // Check if (r_square - i*i)
        // already present in HashMap
        if (mp.has(r_square - i * i)) {
           
            // If it is possible to reach the
            // point (± mp[r_square - i*i], ± i)
            if (Math.max(cntl, cntr)
                >= mp.get(r_square - i * i)
                && Math.max(cntu, cntd) >= i)
 
                return "Yes";
 
            // If it is possible to reach the
            // point (±i, ±mp[r_square-i*i])
            if (Math.max(cntl, cntr) >= i
                && Math.max(cntu, cntd)
                >= mp.get(r_square - i * i))
 
                return "Yes";
        }
    }
 
    // If it is impossible to reach
    return "No";
}
 
// Driver Code
var S = "RDLLDDLDU";
var R = 5;
var N = S.length;
 
document.write( isPossible(S, R, N));
 
 
</script>
Producción: 

Yes

 

Complejidad temporal: O(N + R)
Espacio auxiliar: O(R 2 )

Publicación traducida automáticamente

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