Dada una cuadrícula de tamaño NXM y un robot se coloca en la celda (N – 1, M – 1) . Además, dada la string str que consta solo de los caracteres ‘U’ (arriba), ‘D’ (abajo), ‘L’ (izquierda) y ‘R’ (derecha) que representan los movimientos que el robot va a realizar dentro de la cuadrícula . La tarea es encontrar si el robot estará a salvo al final del último movimiento. Se dice que el robot está a salvo si está dentro de los límites de la cuadrícula.
Nota : Considere que la cuadrícula rectangular está presente debajo de la recta numérica con la esquina superior izquierda sobre el origen.
Ejemplos:
Entrada: N = 1, M = 1, str = “R”
Salida: No
Como solo hay 1 celda, no se permite ningún movimiento.
Entrada: N = 2, M = 3, str = “LLRU”
Salida: Sí
Enfoque: para cada movimiento, actualice la posición del robot dentro de la cuadrícula. si en algún movimiento la posición del robot está fuera de la cuadrícula, la salida será No más imprimir Sí si para todos los movimientos, el robot está dentro de los límites de la cuadrícula.
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 that returns true if the robot is safe
bool isSafe(int N, int M, string str)
{
int coll = 0, colr = 0, rowu = 0, rowd = 0;
for (int i = 0; i < str.length(); i++) {
// If current move is "L" then
// increase the counter of coll
if (str[i] == 'L') {
coll++;
if (colr > 0) {
colr--;
}
// If value of coll is equal to
// column then break
if (coll == M) {
break;
}
}
// If current move is "R" then
// increase the counter of colr
else if (str[i] == 'R') {
colr++;
if (coll > 0) {
coll--;
}
// If value of colr is equal to
// column then break
if (colr == M) {
break;
}
}
// If current move is "U" then
// increase the counter of rowu
else if (str[i] == 'U') {
-rowu++;
if (rowd > 0) {
rowd--;
}
// If value of rowu is equal to
// row then break
if (rowu == N) {
break;
}
}
// If current move is "D" then
// increase the counter of rowd
else if (str[i] == 'D') {
rowd++;
if (rowu > 0) {
rowu--;
}
// If value of rowd is equal to
// row then break
if (rowd == N) {
break;
}
}
}
// If robot is within the bounds of the grid
if (abs(rowd) < N && abs(rowu) < N
&& abs(coll) < M && abs(colr) < M) {
return true;
}
// Unsafe
return false;
}
// Driver code
int main()
{
int N = 1, M = 1;
string str = "R";
if (isSafe(N, M, str))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java implementation of the approach
class GFG {
// Function that returns true if the robot is safe
static boolean isSafe(int N, int M, char[] str)
{
int coll = 0, colr = 0, rowu = 0, rowd = 0;
for (int i = 0; i < str.length; i++) {
// If current move is "L" then
// increase the counter of coll
if (str[i] == 'L') {
coll++;
if (colr > 0) {
colr--;
}
// If value of coll is equal to
// column then break
if (coll == M) {
break;
}
}
// If current move is "R" then
// increase the counter of colr
else if (str[i] == 'R') {
colr++;
if (coll > 0) {
coll--;
}
// If value of colr is equal to
// column then break
if (colr == M) {
break;
}
}
// If current move is "U" then
// increase the counter of rowu
else if (str[i] == 'U') {
rowu++;
if (rowd > 0) {
rowd--;
}
// If value of rowu is equal to
// row then break
if (rowu == N) {
break;
}
}
// If current move is "D" then
// increase the counter of rowd
else if (str[i] == 'D') {
rowd++;
if (rowu > 0) {
rowu--;
}
// If value of rowd is equal to
// row then break
if (rowd == N) {
break;
}
}
}
// If robot is within the bounds of the grid
if (Math.abs(rowd) < N && Math.abs(rowu) < N
&& Math.abs(coll) < M && Math.abs(colr) < M) {
return true;
}
// Unsafe
return false;
}
// Driver code
public static void main(String[] args)
{
int N = 1, M = 1;
String str = "R";
if (isSafe(N, M, str.toCharArray()))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by 29AjayKumar
Python3
# Python 3 implementation of the approach
# Function that returns true
# if the robot is safe
def isSafe(N, M, str):
coll = 0
colr = 0
rowu = 0
rowd = 0
for i in range(len(str)):
# If current move is "L" then
# increase the counter of coll
if (str[i] == 'L'):
coll += 1
if (colr > 0):
colr -= 1
# If value of coll is equal to
# column then break
if (coll == M):
break
# If current move is "R" then
# increase the counter of colr
elif (str[i] == 'R'):
colr += 1
if (coll > 0):
coll -= 1
# If value of colr is equal to
# column then break
if (colr == M):
break
# If current move is "U" then
# increase the counter of rowu
elif (str[i] == 'U'):
rowu += 1
if (rowd > 0):
rowd -= 1
# If value of rowu is equal to
# row then break
if (rowu == N):
break
# If current move is "D" then
# increase the counter of rowd
elif (str[i] == 'D'):
rowd += 1
if (rowu > 0):
rowu -= 1
# If value of rowd is equal to
# row then break
if (rowd == N):
break
# If robot is within the bounds of the grid
if (abs(rowd) < N and abs(rowu) < N and
abs(coll) < M and abs(colr) < M):
return True
# Unsafe
return False
# Driver code
if __name__ == '__main__':
N = 1
M = 1
str = "R"
if (isSafe(N, M, str)):
print("Yes")
else:
print("No")
# This code is contributed by
# Surendra_Gangwar
C#
// C# implementation of the approach
using System;
class GFG {
// Function that returns true if the robot is safe
static bool isSafe(int N, int M, char[] str)
{
int coll = 0, colr = 0, rowu = 0, rowd = 0;
for (int i = 0; i < str.Length; i++) {
// If current move is "L" then
// increase the counter of coll
if (str[i] == 'L') {
coll++;
if (colr > 0) {
colr--;
}
// If value of coll is equal to
// column then break
if (coll == M) {
break;
}
}
// If current move is "R" then
// increase the counter of colr
else if (str[i] == 'R') {
colr++;
if (coll > 0) {
coll--;
}
// If value of colr is equal to
// column then break
if (colr == M) {
break;
}
}
// If current move is "U" then
// increase the counter of rowu
else if (str[i] == 'U') {
rowu++;
if (rowd > 0) {
rowd--;
}
// If value of rowu is equal to
// row then break
if (rowu == N) {
break;
}
}
// If current move is "D" then
// increase the counter of rowd
else if (str[i] == 'D') {
rowd++;
if (rowu > 0) {
rowu--;
}
// If value of rowd is equal to
// row then break
if (rowd == N) {
break;
}
}
}
// If robot is within the bounds of the grid
if (Math.Abs(rowd) < N && Math.Abs(rowu) < N
&& Math.Abs(coll) < M && Math.Abs(colr) < M) {
return true;
}
// Unsafe
return false;
}
// Driver code
public static void Main(String[] args)
{
int N = 1, M = 1;
String str = "R";
if (isSafe(N, M, str.ToCharArray()))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of the approach
// Function that returns true if the robot is safe
function isSafe(N, M, str)
{
var coll = 0, colr = 0, rowu = 0, rowd = 0;
for (var i = 0; i < str.length; i++) {
// If current move is "L" then
// increase the counter of coll
if (str[i] == 'L') {
coll++;
if (colr > 0) {
colr--;
}
// If value of coll is equal to
// column then break
if (coll == M) {
break;
}
}
// If current move is "R" then
// increase the counter of colr
else if (str[i] == 'R') {
colr++;
if (coll > 0) {
coll--;
}
// If value of colr is equal to
// column then break
if (colr == M) {
break;
}
}
// If current move is "U" then
// increase the counter of rowu
else if (str[i] == 'U') {
-rowu++;
if (rowd > 0) {
rowd--;
}
// If value of rowu is equal to
// row then break
if (rowu == N) {
break;
}
}
// If current move is "D" then
// increase the counter of rowd
else if (str[i] == 'D') {
rowd++;
if (rowu > 0) {
rowu--;
}
// If value of rowd is equal to
// row then break
if (rowd == N) {
break;
}
}
}
// If robot is within the bounds of the grid
if (Math.abs(rowd) < N && Math.abs(rowu) < N
&& Math.abs(coll) < M && Math.abs(colr) < M) {
return true;
}
// Unsafe
return false;
}
// Driver code
var N = 1, M = 1;
var str = "R";
if (isSafe(N, M, str))
document.write( "Yes");
else
document.write( "No");
</script>
Producción:
No
Complejidad de tiempo: O(|str|)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Naman_Garg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA